다익스트라나 벨만-포드 알고리즘들은 모두 한 시작점에서 다른 모든 정점까지의 거리를 구해 줍니다. 하지만 문제에 따라서는 한 개의 시작점 대신 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구해야 할 때도 있습니다. 이런 문제를 해결하는 가장 간단한 방법은 각 정점을 시작점으로 다익스트라 알고리즘을 반복해서 실행하는 것입니다. 만약 음수 가중치가 있다면 벨만-포드 알고리즘을 사용하면 되구요.
그러나 모든 쌍 간의 최단 거리를 구하고 싶다면 이것보다 좀더 빠르고 간단한 방법이 플로이드(Floyd)의 모든 쌍 최단 거리 알고리즘입니다. 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][] 계산합니다. 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타냅니다.
정점 집합 S에 포함된 정점만을 경유점으로 사용해 u에서 v로 가는 최단 경로의 길이를 Ds(u, v)라고 하고, 이 최단 경로를 알고있다고 합시다. S 중에 정점을 하나 골라 x라고 하면, 최단 경로는 x를 경유할 수도 있고 경유하지 않을 수도 있습니다. 각 경우에 최단 경로는 어떤 형태를 가질까요?
- 경로가 x를 경유하지 않는다: 이 경로는 S - {x} 에 포함된 정점들만을 경유점으로 사용합니다.
- 경로가 x를 경유한다: 이 경로를 u에서 x로 가는 구간과 x에서 v로 가는 구간으로 나눌 수 있습니다. 이 두 개의 부분 경로들은 각각 u와 x, x와 v를 잇는 최단 경로들이어야 합니다. 당연하게도 두 개의 부분 경로들은 x를 경유하지 않으며, 따라서 S - {x} 에 포함된 정점들만을 경유점으로 사용합니다.
S를 경유점으로 사용해 u에서 v로 가는 최단 경로는 위 두 가지 중 더 짧은 경로가 되겠지요. 따라서 Ds(u, v)를 다음과 같이 재귀적으로 정의할 수 있습니다.
Ds(u, v) = min(Ds-{x}(u, x) + Ds-{x}(x, v), Ds-{x}(u, v))
Sk = {0, 1, 2, …, k}라고 두고, Ck = Dk라고 합시다. 그러면 Ck(u, v)는 0번 정점부터 k번 정점까짐나을 경유점으로 썼을 때 u에서 v까지 가는 최단 경로의 길이가 됩니다. 아래 코드에서 Ck(u, v)의 값은 C[k][u][v]에 저장됩니다. 따라서 함수의 종료 후에 u에서 v로 가는 최단 거리를 알려면 C[V-1][u][v]를 보면 됩니다.
// 정점의 개수
int V;
// adj[u][v] = u에서 v로 가는 간선의 가중치. 간선이 없으면 아주 큰 값을 넣는다.
int adj[MAX_V][MAX_V];
int C[MAX_V][MAX_V][MAX_V];
void allPairShortestPath1() {
// C[0]을 초기화
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
if (i != j) C[0][i][j] = min(adj[i][j], adj[i][0] + adj[0][j]);
else C[0][i][j] = 0;
// C[k-1]이 있으면 C[k]를 계산할 수 있다.
for (int k = 1; k < V; ++k)
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
C[k][i][j] = min(C[k-1][i][j], C[k-1][i][k] + C[k-1][k][j]);
}
마지막에 C[V-1][u][v]가 아주 큰 값 이상이라면 경로가 존재하지 않음을 알 수 있습니다. C[0]을 계산할 때 C[0][u][u]는 항상 0으로 초기화합니다. 자기 자신으로 가는 간선이 따로 없더라도 최단 거리는 항상 0이기 때문입니다. 이 알고리즘의 시간 복잡도는 3중 for문이 지배합니다. 각각은 O(|V|)번 수행되기 때문에 전체 시간 복잡도는 O(|V|^3)이 됩니다.