Shortest Path Algorithm - Floyd-Warshall

Floyd-Warshall

플로이드 워셜 알고리즘(흔히 플로이드라고 부른다)은 그래프에서 모든 정점 사이의 최단경로 및 최단거리를 구하는 알고리즘이다. Bellman-Ford, Dijkstra와는 다르게 한 정점으로부터 나머지 모든 정점으로의 최단경로가 아닌 모든 정점 사이의 최단경로를 구할 수 있으며, 음수 사이클이 없는 그래프라면 음수 가중치가 있어도 동작한다.

플로이드 알고리즘은 다음과 같은 점화식에 기반하고 있다.

정점의 수가 V인 그래프에서 플로이드의 점화식

D[i][j] = (정점 i로부터 정점 j로의 최단거리)

D[i][j] = min(D[i][j], D[i][k] + D[k][j]) (1 <= k <= V)

초기값 - 각 간선이 정점 A, B를 C의 거리로 잇고 있다고 할 때, D[A][B] = C

위 점화식이 의미하는 바는 이렇다.

정점 i로부터 정점 j로의 최단거리는, 모든 정점 k에 대해 i에서 k를 거쳐 j로 이동하는 최단거리들 중 최솟값이다.

점화식만 본다면 꽤나 당연한 듯 보일 수도 있겠다. 하지만, 플로이드는 정말로 비직관적인 알고리즘이다(적어도 필자는 그렇게 생각한다). 위 점화식을 모두 채우기 위해서는 모든 정점쌍 (i, j)와 모든 정점 k에 대해 점화식을 수행해야 하며, 그 수행 과정에서 k를 정해놓은 이후 모든 정점쌍 (i, j)에 대해 수행해야 한다. 

코드로 표현하면 다음과 같다.

for(k = 1; k <= V; k++){

for(i = 1; i <= V; i++){

for(j = 1; j <= V; j++){

D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

}

}

}

(위 코드에서 k를 결정하는 순서를 오름차순으로 구현하였으나, 실제로는 어떠한 순서로 잡아도 상관없다.)

그럼, 왜 경유정점 k를 고정시켜 놓은 후 모든 정점쌍 (i, j)를 잡아서 플로이드를 수행하면, 모든 정점쌍간의 최단경로, 거리가 구해지는지 증명해보겠다.

위 그림과 같은 그래프가 있다.

붉게 칠한 점을 경유정점으로 잡아서 모든 정점쌍에 대해 플로이드를 수행한다고 하면

붉은색으로 영역을 표시한 구역 내에 있는 간선들과 정점들로 이루어진 부분그래프 내에서, 그 그래프 내에 있는 간선들을 이용한 부분그래프 내의 모든 정점사이의 최단경로와 거리가 구해진다. (임의의 정점이 경유정점과 이어져있을 경우, 경유정점과 이어져있는 다른 정점으로의 최단거리(경유 정점과 이어진 간선들만 사용한 경우의)가 구해진다.)

새로, 푸른색으로 칠해진 정점을 경유정점으로 잡고 플로이드를 수행하면

푸른색으로 영역이 그려진 부분그래프 내의 모든 간선들만 이용한, 부분그래프 내의 모든 정점 사이의 최단경로가 구해진다.

이후, 보라색 정점을 경유정점으로 잡아서 수행하면

보라색 영역 내에 있는 모든 간선들을 이용한, 부분그래프 내의 모든 정점 사이의 최단경로가 구해진다.

이는 처음에 각각의 모든 간선들로 이어진 정점들과 간선을 부분집합이라고 보았을 때(초기화 과정에서 구해진 것), 임의의 정점을 경유정점으로 잡고 플로이드를 수행하면, 그 정점을 포함하는 부분그래프들을 모두 합친 새로운 부분그래프의 최단경로를 구할 수 있음을 알 수 있다. (그림이 상당히 난해하다)

이를 설명하기가 상당히 어려운데, 부분그래프가 존재한다면, 그 부분그래프 내에 있는 모든 간선들을 이용한 부분그래프 내 모든 정점사이의 최단경로를 구할 수 있다고 가정하자.

붉은 영역, 푸른 영역, 보라색 영역이 각각의 부분그래프이고, 가정을 만족한다.

그 상황에서 위와 같은 검은 정점을 경유정점 K로 잡는다고 하면, 붉은색 영역 내의 모든 정점은 내부의 간선을 이용하여 붉게 칠한 정점으로 이동하는 최단경로가 구해져있고, 나머지 색상도 마찬가지이다. 

이 때, 붉은 영역에서 임의의 점과 경유정점을 잇는 최단경로를 알고있고(붉은 영역 내의 간선을 이용한), 보라색 영역에서 임의의점과 경유정점을 잇는 최단경로를 알고있다. 즉, 붉은 영역의 임의의 점 A와 보라색 영역의 임의의 점 B에 대해

D[A][B] = D[A][K] + D[K][B]

에 해당하는 경로를 알아낼 수 있다. (A와 B사이의 최초의 경로를 발견)

이를 통해 정점 A와 정점 B로의 검은 간선과 붉은 영역 내 간선, 보라색 영역 내 간선들을 이용한 최단경로를 구할 수 있다. 이를 모든 색상에 대해 갱신해주면, 붉은 영역, 파란 영역, 보라색 영역에 해당하는 모든 정점쌍간의 최단경로를 구할 수 있고, 이는 검은 정점이 속해있는 모든 부분그래프를 합친 그래프 내에 있는 간선들을 이용한 모든 정점쌍의 최단경로를 알아내는 것과 같다. 즉, 경유정점을 잡고 모든 정점 사이에 대해 플로이드를 수행함으로써 그 정점이 속해있는 부분그래프들을 합치는 것으로 볼 수 있다. 이로 인해 새로 생긴 부분그래프 내에 있는 모든 간선들을 이용한 부분그래프 내 모든 정점사이의 최단경로를 구할 수 있음이 보장되고, 경유정점을 포함하는 부분그래프들을 모두 합쳐짐을 알 수 있다.

이를 보이면 모든 경유정점을 잡음으로 부분그래프들이 다 하나로 합쳐짐을 알기는 쉽다. 임의의 간선은 처음에 양 끝 정점을 포함한 부분집합으로 합쳐져 있으며, 모든 경유정점을 볼 경우, 각 간선들의 양쪽 정점을 모두 보는 것과 같다. 즉, 모든 처음의 부분집합은 정점과 이어진 다른 부분집합과 무조건 합쳐짐을 알 수 있고, 그래프에서 임의의 정점과 정점사이의 경로가 존재함으로 결국 처음에 만든 모든 부분집합이 합쳐진다.

경유정점을 선택하고, 모든 정점에 대해 수행할 경우, 플로이드의 시간복잡도는 정점 수 V의 세제곱에 비례한다.

따라서, 플로이드-와셜 알고리즘의 시간복잡도는 O(V^3)이다.