그래프 (5) - 임의의 두 정점 간 최단 경로(플로이드-워셜)

앞서 4편에서는 하나의 출발점으로부터 각 정점의 최단경로를 구하는 알고리즘들에 대하여 알아보았다. 이번에는 임의의 두 정점 간 최단경로를 구하는 방법에 대해 알아보자.

 

 

플로이드-워셜

모든 정점 간의 최단 거리가 필요할 때 가장 널리 사용되는 알고리즘이 플로이드-워셜(Floyd-Warshall) 알고리즘이다. 플로이드-워셜 알고리즘의 아이디어는 단순하다. $k$번 정점을 거쳐갈지 말지를 기준으로, 다음과 같은 점화식을 이용해 정점 $a$와 $b$ 간의 최단 거리를 구하게 된다.

 

$$dist[a][b]=\min(dist[a][b], dist[a][k] + dist[k][b])$$

 

따라서 인접 행렬을 이용해서 그대로 구현할 수 있다. 자기 자신으로 이동하는 거리는 0, 간선이 이어져 있지 않은 배열의 나머지 공간은 $\infty$로 정의한 후 k, a, b를 1~V까지 반복하면 된다. 임의의 두 점 간의 최단경로는 정점을 V개 이하로 지나게 되므로 $O(V^3)$만에 충분히 모든 점에 대한 최단거리를 구할 수 있다.

 

adj = [[float('inf')]*(N+1) for _ in range(N+1)]
for i in range(1, N+1): adj[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    if adj[a][b] > c:
        adj[a][b] = c

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            adj[a][b] = min(adj[a][b], adj[a][k] + adj[k][b])

 

 

존슨 알고리즘

희소 그래프에 대해, 시간복잡도를 $O(V^2\log V  + VE)$로 개선시킨 알고리즘이 존슨 알고리즘이다. 벨만-포드 알고리즘을 수행한 후 모든 점에 대해 다익스트라를 적용해 임의의 두 점간 최단경로를 구하게 된다. 다소 복잡한데 그렇게 자주 사용되지는 않는 것 같아 언급만 하고 넘어가도록 하겠다.