[Algorithm] Floyd-Warshall Algorithm (플로이드-워셜)

앞선 Dijkstra 알고리즘이나, Bellman-Ford 알고리즘은 하나의 Source 에서 다른 모든 vertex 들 간에 shortext path를 구하는 알고리즘입니다. 이와 같은 문제를 single-source shortest path problem 이라고 합니다.

 

단일 source 가 아닌 임의의 모든 두 vertex u, v 에 대해 u에서 v로의 shortest path를 구하는 문제를 all-pairs shortest path problem 이라고 합니다. Directed Graph G = (V, E) 가 (undirected graph의 경우 bellman-ford 알고리즘과 같은 방법으로 directed graph로 변환하여) negative cycle이 없는 경우 G에서 all-pairs shortest path problem 은 G의 각 vertex를 source로 둔 다음, 해당 source에 대해 Bellman-ford 알고리즘을 수행하면 해결할 수 있습니다. 즉, Bellman-ford 알고리즘을 vertex 개수만큼 돌리면 됩니다. 이 경우, all-pairs shortest path problem 을 해결하는 알고리즘의 시간 복잡도는 o(n * nm) = O(n^2m) 이 됩니다.

 

더 빠른 알고리즘은 없을까요?

 

Floyd-Warshall Algorithm

다이나믹 프로그래밍을 이용하여 all-pairs shortest path 를 해결하는 알고리즘

 

플로이드-워셜 알고리즘도 다이나믹 프로그래밍 기반이므로 다음과 같이 Recurrence Relation 을 세울 수 있습니다.

 

V = {1,2,...,n} 으로 두고, G의 임의의 두 Vertex i,j에 대해 dist(i,j,k)를 vertex {1,2,...,k} 만을 path 의 중간 거점 vertex 로 포함시킬 수 있을 때, i에서 j로의 shortest path 의 길이라 정의하겠습니다.

 

Proof
Base Case (k=0) :

dist(i, j, 0) = 0 <- i = j 인 경우

dist(i, j, 0) = w(i, j) <- edge(i, j)가 존재하는 경우

dist(i, j, 0) = INF <- edge(i, j)가 존재하지 않는 경우.

 

Inductive Step : dist(i, j, k)의 길이를 가진 path를 두가지 case로 나누어보겠습니다.

Case 1 : vertex k 를 지나치지 않는 경우 (즉 vertex k를 중간 기점으로 사용 가능해도, vertex {1,...,k-1} 을 중간 기점으로 사용할 때와 비교해서 shortest path 의 길이가 줄어들지 않는 경우) dist (i, j, k) = dist(i, j, k-1).

 

Case 2: vertex k 를 지나는 경우 dist(i, j, k) = dist(i, k, k-1) + dist(k, j, k-1) 이 됩니다. 왜냐하면 G는 negative cycle을 포함하지 않으므로 i에서 k로의 path와 k에서 j로의 path는 서로 같은 vertex를 중간에 포함하고 있지 않기 때문입니다.

 

Case 1과 Case 2를 비교하여 더 작은 경우를 dist(i, j, k)로 둡니다. 따라서 dist(i,j,k) = min(dist(i, k, k-1) + dist(k, j, k-1), dist(i,j,k-1)) 이 됩니다. 최종적으로 vertex i에서 j까지의 shortest path의 길이는 dist(i,j,n)이 됩니다.

 

Floyd-Warshall 의 개요는 다음과 같게 됩니다.

1. 플로이드-워셜 알고리즘은 총 0~n 의 stage로 구성되며, k번째 stage가 끝날 때마다 G의 모든 vertex i,j에 대해 dist(i,j,k)가 dist(i,j)에 저장됩니다.

2. 0번째 stage에서는 앞선 base case 에 맞게 dist 값을 정해줍니다.

3. 이후 k번째 stage 마다 모든 vertex i,j에 대해 다음 작업을 반복합니다. dist(i,j,k) = min(dist(i, k, k-1) + dist(k, j, k-1), dist(i,j,k-1))

 

시간 복잡도 분석

각 Stage마다 모든 1 <= i,j <= n 에 대해서 dist(i,j)를 업데이트 * (n+1)개의 stage

=> O(n^2 * (n+1)) = O(n^3)

(m = Ω (n) 인 경우, Bellman-Ford 알고리즘을 n 번 반복하는 것보다 더 빠르다)