[알고리즘] 모든 쌍에 대한 최단 경로 구하기

최단 경로를 구하는 알고리즘을 이용하여 모든 쌍에 대해 최단 경로를 구하도록 코드를 구현해보자

 

1. Dijkstra 알고리즘 이용

다익스트라 알고리즘은 Greedy 알고리즘을 이용하여 현재 선택된 정점 그래프에서 다음 노드까지의 가중치가 제일 적은 노드를 선택 > MST의 Prim's Algorithm과 유사

 

• MST와 유사하지만 모든 정점을 시작 정점으로 선택하도록 반복해야함
• 거리와 방문 여부를 체크해야함 > 거리는 그래프 안에서 찾기 

 

 

import time # 실 실행시간 측정을 위한 타임 모듈 추가

INF=int(1e9) # 무한대 설정
n, m = map(int, input().split()) # 정점의 개수(n), 간선의 개수(m) 입력

graph = [[INF] * n for _ in range(n)] # 그래프는 2차원 배열로 길이를 저장

for _ in range(m):
  u, v, w = map(int,input().split())  # 출발 정점(u), 도착 정점(v), 가중치(w)
  graph[u - 1][v - 1] = w
  graph[v - 1][u - 1] = w  # 양방향으로 가중치를 추가

start = time.time() # 처음 실행 시간

def dijkstra(graph, start): # 그래프와 시작 정점을 입력받고
  n = len(graph)
  dist = [INF] * n
  dist[start] = 0
  visited = [False] * n # 다른 정점의 방문 리스트를 설정

  for i in range(n):
    min_dist = INF
    min_index = -1

    for j in range(n):
      if not visited[j] and dist[j] < min_dist:
          min_dist = dist[j]
          min_index = j

    visited[min_index] = True # 방문을 했으면 리스트 설정

    for j in range(n):
      if not visited[j] and graph[min_index][j] != INF:
         new_dist = dist[min_index] + graph[min_index][j]
         if new_dist < dist[j]:
            dist[j] = new_dist

  return dist # 길이 리스트 반환

# 각 정점에서 모든 다른 정점까지의 최단 경로 계산
for i in range(n):
  shortest_paths = dijkstra(graph, i)
  for j, distance in enumerate(shortest_paths):
    if j>=i:
      if distance == INF:
          print(" X", end='')
      else:
          print('%2d' % distance,end=' ')
    else:
      print(' X',end=' ')
  print()
end=time.time() # 실행을 마친 시간
print(end-start) # 실행 시간 출력

 

 

 

2. Floyd-warshall 알고리즘 이용

Floyd-warshall 알고리즘의 경우 dijkstra 알고리즘과 다르게 동적계획법(Dynamic Programming)을 사용한 알고리즘이다

Floyd-Warshall 알고리즘의 아이디어 :

• 3개의 점이 있는 경우에서 바로 가는 경우와 / 중간에 다른 점을 거쳐 가는 경우 중 짧은 경로를 선택
• 해당 알고리즘을 점점 키워가는 동적계획법

i점에서 j점을 가기위해서는 i부터 k / k부터 j의 값을 알아야함

 

 

import time # 실 실행시간 측정을 위한 타임 모듈 추가
INF = int(1e9) # 무한대 설정

n,m = map(int, input().split())  # 정점의 개수(n), 간선의 개수(m) 입력
graph = [[INF]*(n+1) for _ in range(n+1)] # 그래프는 2차원 배열로 길이를 저장

for i in range(1,n+1):
  graph[i][i]=0

for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a][b] = c
  graph[b][a] = c # 양방향으로 그래프 가중치 입력

start = time.time()

# 플로이드 워셜 알고리즘
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      if i!=j:
        graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])

# 완료한 배열을 출력
for i in range(1, n+1):
  graph[i][i]=0
  for j in range(1, n+1):
    if i<=j:
      if graph[i][j] == INF:
          print(" X", end='')
      else:
          print('%2d' % (graph[i][j]),end=' ')
    else:
      print(" X", end=" ")
  print()

end=time.time()
print(end-start)

 

 

3. 코드 결과 비교

두 코드의 방법은 다르지만 각 코드의 시간 복잡도는 O(n³)이다

또한, 각 출력 역시 같은 출력 값을 가지게 된다

물론, 다익스트라의 코드보다 플로이드 워셜의 코드가 더 단순하기에 실 실행시간은 플로이드 워셜이 더 짧은 경우가 많음 ( 실행하는 여러 조건에 따라서 달라질 수 있습니다 )

 

모든 쌍에 대해 최단 경로를 구하는 방법을 알아보았습니다
현재 코드는 무방향 그래프로 설정되어 있지만 조금의 수정을 통해 방향이 있는 그래프 역시도 같은 방법으로 실행이 가능할 것입니다