모든 정점 쌍 사이의 최단거리를 한 번에 구한다. 다익스트라가 한 시작점에서 나머지 전부를 구하는 것과 대비된다. 발상은 한 줄이다. A에서 B로 바로 가는 것보다 X를 거쳐 가는 것이 짧으면 그 값으로 바꾼다.
경유지를 바깥에 두는 삼중 반복
정점 수 곱하기 정점 수 크기의 배열을 무한대로 채우고, 간선에 적힌 값을 해당 칸에 적는다. 그 다음 경유지를 1번 정점으로 놓고 모든 쌍 (i, j)에 대해 dist[i][j] > dist[i][k] + dist[k][j]면 갱신한다. 경유지를 2번, 3번, N번으로 바꿔가며 같은 일을 반복한다.
for (int k = 1; k <= N; k++) // 경유지가 바깥
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);반복문 순서가 k, i, j여야 하는 것이 가장 많이 틀리는 지점이다. 바깥 반복이 경유지여야 하는 이유는, 이 알고리즘이 1번까지만 경유해도 되는 최단거리에서 2번까지 경유해도 되는 최단거리로 답을 넓혀가기 때문이다. i, j를 바깥에 두면 아직 계산되지 않은 값을 참조하게 되어 틀린 답이 나온다.
다익스트라를 반복하는 것과의 비용
모든 쌍을 알아야 한다면 다익스트라를 정점마다 한 번씩 돌리는 방법도 있다. 그 비용은 우선순위 큐를 쓸 때 O(V × E log V)다.
그런데 간선이 빽빽하면 E가 V²에 가까워지므로 O(V³ log V)가 되어 플로이드-워셜의 O(V³)보다 나빠진다. 정점이 적거나 간선이 조밀하면 플로이드-워셜, 정점이 많고 간선이 희소하며 시작점이 하나면 다익스트라다.
음수 간선이 있어도 쓸 수 있다는 것도 차이다. 다익스트라는 못 쓴다.
V³ 시간과 V² 공간
삼중 반복문이니 O(V³)이고, 공간도 O(V²)라 정점이 조금만 많아져도 배열을 못 잡는다. 상당히 비효율적이라 정점 수가 많지 않거나 모든 쌍의 최단거리를 꼭 구해야 할 때만 쓴다. 공간복잡도에서 막히는 대표적인 알고리즘이다.