모든 쌍 최단 거리 — 다익스트라 N번과 플로이드·워셜

다익스트라 1은 시작점 하나를 정하고 거기서 모든 노드까지의 거리를 구했다. 이번엔 시작점을 고르지 않는다. 모든 쌍이다. 답이 하나가 아니라 $N^2$ 개다.

이 포스트에서 다루는 내용

다익스트라를 $N$ 번 돌리는 기준선과 그 복잡도
경유할 수 있는 노드를 $\{1,\dots,k\}$ 로 제한하는 전략
점화식 $D^k[i][j] = \min(D^{k-1}[i][j],\ D^{k-1}[i][k]+D^{k-1}[k][j])$ 의 양방향 증명
3차원 배열 의사코드

무엇을 구하는가

입력은 무방향 가중 그래프이고 노드 수를 $N$ , 간선 수를 $M$ 이라 한다. 모든 간선의 가중치는 $0$ 이상이라고 둔다. 무방향 그래프에서 음수 간선 하나는 그 간선을 오가는 음수 사이클과 같아서, 왕복할수록 길이가 줄어드는 길이 생기고 최단 거리라는 말 자체가 성립하지 않는다. 비음수 전제는 뒤에서 점화식을 세울 때 다시 쓰인다.

구하려는 값은 노드 $i$ 에서 노드 $j$ 까지의 최단 거리다.

$i$ 와 $j$ 를 각각 $N$ 가지로 고를 수 있으니 답은 $N^2$ 개이고, 출력은 자연스럽게 $N \times N$ 행렬 한 장이 된다. 다익스트라가 채우던 것이 이 행렬의 한 줄이었다면 이번에는 행렬 전체다.

이 글은 최단 거리만 다룬다. 그 거리를 내는 길이 어떤 노드를 어떤 순서로 밟는지, 즉 경로 자체를 복원하는 문제는 여기서 다루지 않는다.

방향 그래프에서도 아이디어는 그대로 쓸 수 있다. 행렬이 대칭이 아니게 될 뿐이라 이 글에서는 더 파고들지 않는다.

다익스트라를 N번 돌리면

다익스트라는 시작점 하나를 정하면 거기서 모든 노드까지의 최단 거리를 한 번에 준다. 필요한 답이 모든 쌍이니 시작점을 $1$ 번부터 $N$ 번까지 바꿔 가며 $N$ 번 돌리면 행렬의 모든 줄이 채워진다. 새로 배울 것 없이 답은 나온다.

비용을 재 보자. 우선순위 큐를 이진 힙으로 구현하면 다익스트라 한 번은 $O((M+N)\log N)$ 이다. 이를 $N$ 번 반복하니 전체는 $O(N(M+N)\log N)$ 이다.

식 안의 $M+N$ 은 더 줄일 수 있다. 모든 노드가 서로 이어져 있는 연결 그래프라면 간선이 적어도 노드 수보다 하나 적은 만큼은 있다. 기호로 쓰면 $M \ge N-1$ , 곧 $M$ 이 $N-1$ 보다 크거나 같다.

이 부등식을 옮기면 $N \le M+1$ , 곧 $N$ 이 $M+1$ 을 넘지 않는다. 양변에 $M$ 을 더하면 $M+N \le 2M+1$ 이다.

$O(\cdot)$ 표기는 상수배와 상수항을 세지 않는다. $M+N$ 자리에 그냥 $M$ 을 써도 된다는 뜻이고, 전체는 $O(NM\log N)$ 으로 정리된다.

이 식은 그래프에 따라 크게 달라진다. $M$ 자리에 실제 간선 수를 넣어 보면 안다.

모든 노드가 서로 이어진 빽빽한 그래프라면 간선은 대략 $N^2$ 개다. $O(NM\log N)$ 의 $M$ 에 $N^2$ 을 넣으면 $O(N \cdot N^2 \log N)$ , 즉 $O(N^3\log N)$ 이다.

반대로 노드마다 이웃이 몇 개뿐인 성긴 그래프라면 간선 수가 노드 수와 비슷해 대략 $N$ 개다. 같은 자리에 $N$ 을 넣으면 $O(N \cdot N \log N)$ , 즉 $O(N^2\log N)$ 이다.

같은 알고리즘을 같은 횟수 돌려도 그래프 모양에 따라 $N$ 배가 갈린다.

새 알고리즘이 놓일 자리

새 알고리즘을 배우기 전에 그 알고리즘이 놓일 만한 자리를 먼저 가늠해 볼 수 있다.

한쪽 끝은 다익스트라 한 번, 즉 $O(M\log N)$ 이다. 모든 쌍을 구하는 알고리즘이 이보다 빠르다면 한 쌍의 거리만 필요한 상황에서도 그 알고리즘을 돌려 원하는 칸을 꺼내면 된다. 다익스트라가 설 자리를 잃는다.

다른 쪽 끝은 방금 계산한 $O(NM\log N)$ 이다. 새 알고리즘이 이보다 느리다면 다익스트라를 $N$ 번 돌리는 쪽이 나으니, 굳이 새 알고리즘을 배울 이유가 없다.

쓸모 있는 알고리즘이라면 $O(M\log N)$ 과 $O(NM\log N)$ 사이 어딘가에 놓이리라 생각해 볼 수 있다. 증명된 하한이 아니라 무엇을 기대하며 다음 절을 읽을지 정하는 눈금이다.

지나갈 수 있는 노드를 제한한다

노드에 $1$ 번부터 $N$ 번까지 번호를 붙인다. 번호는 아무렇게나 붙여도 되며, 이 번호가 곧 계산 순서가 된다.

이제 값 하나에 이름을 붙인다. 이름이 담아야 할 것은 셋이다. 어디서 출발하는지, 어디로 가는지, 도중에 몇 번 노드까지 밟아도 되는지.

$D^k[i][j]$ 를 “ $i$ 에서 $j$ 로 가되 중간에 거치는 노드가 모두 $\{1,\dots,k\}$ 안에 있는 길 중 최단 거리”로 정의한다.

기호를 뜯어 보면 이렇다. 대괄호 안의 $i$ 와 $j$ 가 출발점과 도착점이고, 위첨자 $k$ 가 허용 범위다. $\{1,\dots,k\}$ 는 1번부터 $k$ 번까지의 노드를 한데 모아 놓은 집합을 가리킨다.

제한을 받는 대상은 중간 노드뿐이다. 출발점 $i$ 와 도착점 $j$ 는 끝점이라 번호가 $k$ 보다 크더라도 상관없다.

제한은 “쓸 수 있다”이지 “반드시 써야 한다”가 아니다. $D^2[i][j]$ 를 겨루는 길은 1번과 2번을 마음대로 거쳐도 되고 하나도 거치지 않아도 된다. $k$ 가 커지면 후보가 늘어날 뿐 줄지 않는다.

$k$ 를 $0$ 에서 $N$ 까지 한 칸씩 늘린다. 눈여겨볼 것은 양쪽 끝이다.

$k=0$ 이면 중간 노드를 하나도 쓸 수 없어 직행 간선만 남는다. $k=N$ 이면 모든 노드가 허용되어 제한이 사라진다. 제한 없는 최단 거리, 즉 우리가 찾던 답이 $D^N[i][j]$ 다.

k가 0, 1, 2로 커지면서 중간에 지나갈 수 있는 노드 집합이 넓어진다.

손으로 따라가기

노드 4개짜리 그래프로 $k$ 를 늘려 본다. 간선과 가중치는 다음과 같다.

$1{-}2:1$ , $1{-}3:5$ , $1{-}4:7$
$2{-}4:1$ , $3{-}4:10$

2번과 3번을 잇는 간선은 없다.

$k=0$ . 중간 노드를 하나도 못 쓰니 직행 간선의 가중치가 그대로 값이 된다. 간선이 없는 쌍은 $\infty$ , 대각선은 $0$ 이다.

$k=1$ . 1번을 거쳐도 된다. $(2,3)$ 은 직행 간선이 없어 $\infty$ 였는데 $2\to1\to3$ 이 $1+5=6$ 이므로 $6$ 으로 내려간다.

모든 쌍이 내려가지는 않는다. $(3,4)$ 는 $3\to1\to4$ 가 $5+7=12$ 로 직행 $10$ 보다 길다. 이 쌍은 1번을 쓰지 않는다.

$k=2$ . 1번과 2번을 모두 거칠 수 있다. 따져야 할 길이 $i\to j$ , $i\to1\to j$ , $i\to2\to j$ , $i\to1\to2\to j$ , $i\to2\to1\to j$ 로 늘어난다.

값이 내려가는 칸은 둘이다. $(1,4)$ 가 $1\to2\to4 = 1+1$ 로 $7$ 에서 $2$ 가 되고, $(3,4)$ 가 $3\to1\to2\to4$ 로 $10$ 에서 $7$ 이 된다.

핵심 관찰

$k=1$ 에서 쓰지 않은 노드가 $k=2$ 에서 쓰일 수 있다. $3\to4$ 는 $k=1$ 에서 1번을 거치는 길이 더 길어 1번을 버렸지만, $k=2$ 에서 $3\to1\to2\to4 = 5+1+1 = 7$ 로 1번이 되살아난다. 2번이 열리면서 1번을 거치는 값어치가 달라졌기 때문이다.

각 단계가 기록하는 값은 “그 노드를 쓸지”에 대한 결정이 아니라 “그 집합까지 허용했을 때의 최선”이다. 단계마다 노드를 하나씩 확정해 나간다고 읽으면 이 예시에서 바로 틀린다.

$k=3$ 과 $k=4$ 에서는 바뀌는 칸이 없다. 3번이나 4번을 중간에 끼워 더 짧아지는 쌍이 남아 있지 않기 때문이다. 최종 행렬은 다음과 같다.

	1	2	3	4
1	0	1	5	2
2	1	0	6	1
3	5	6	0	7
4	2	1	7	0

점화식 세우기

갖출 부품은 둘이다. 맨 아래층을 직접 정하는 기저와, 아래층에서 윗층을 얻는 점화식이다. 기저부터 본다.

$k=0$ 은 계산할 것이 없다. $D^0[i][j]$ 는 중간 노드를 하나도 쓰지 못하는 값이므로 간선 가중치 그 자체이고, 간선이 없으면 $\infty$ , $i=j$ 면 $0$ 이다. 입력을 그대로 옮겨 적으면 기저가 완성된다. 동적 계획법에서 표의 첫 줄을 정의로 채우고 나머지를 점화식으로 밀어 올리던 구도와 같다.

채워야 할 칸은 첨자 $k$ , $i$ , $j$ 가 각각 $N$ 가지 안팎이니 $N \times N \times N$ , 곧 $O(N^3)$ 개다. 남은 일은 $k$ 층의 한 칸을 $k-1$ 층에서 어떻게 얻느냐다.

그 전에 정리 하나가 필요하다. 길을 두 조각으로 자르는 논증이 뒤에 나오는데, 같은 노드가 여러 번 등장하면 어디서 잘라야 할지가 정해지지 않는다. 우리가 다루는 값은 $D^k$ 처럼 중간 노드를 제한한 최단 거리이므로, 정리도 그 제한을 단 채로 세워 둔다.

증명의 얼개는 간단하다. 같은 노드가 두 번 나오면 그 사이를 통째로 잘라내고, 잘라낸 길이 여전히 제한을 지키며 더 길어지지도 않았음을 확인한다.

정리 1중복 노드 없는 길로 바꾸기

간선 가중치가 모두 $0$ 이상이면, 중간에 거칠 수 있는 노드를 어떤 집합 $S$ 로 제한할 때, 그 제한을 지키며 $i$ 에서 $j$ 로 가는 길은 어느 것이든 같은 노드를 두 번 지나지 않는 길로 바꿀 수 있다. 바꾼 길도 같은 제한을 지키고, 길이는 원래보다 늘지 않는다.

$S$ 를 전체 노드 집합으로 두면 제한이 없는 경우도 여기에 들어간다.

증명. 제한 $S$ 를 지키는 길 $Q$ 를 하나 잡는다. 최단이라는 조건은 걸지 않는다. $Q$ 위에 어떤 노드 $a$ 가 두 번 나온다고 하자. 두 등장 사이의 구간은 $a$ 에서 출발해 $a$ 로 돌아오는 닫힌 구간이다.

이 구간을 통째로 잘라내면 잘린 자리의 앞뒤가 모두 $a$ 이므로 그대로 이어지고, 남은 것은 여전히 $i$ 에서 $j$ 로 가는 길이다. 잘라낸 길의 중간 노드는 $Q$ 의 중간 노드에서 몇 개를 덜어낸 것이라 새로 등장하는 노드가 없으므로, 여전히 모두 $S$ 안에 있다. 곧 잘라낸 길도 같은 제한 아래의 후보다. 잘라낸 구간의 길이는 간선 가중치의 합인데 가중치가 모두 $0$ 이상이므로 그 합도 $0$ 이상이다. 비음수 전제가 쓰이는 자리가 여기다. 곧 잘라낸 뒤의 길이는 원래보다 늘지 않는다.

같은 노드가 아직 남아 있으면 같은 잘라내기를 반복한다. 닫힌 구간에는 간선이 최소 하나 있으므로 한 번 잘라낼 때마다 길 위의 노드 등장 횟수가 최소 하나 줄어든다. 이 횟수는 음이 아닌 정수라서 무한히 줄어들 수 없고, 잘라내기는 유한 번에 멈춘다. 멈춘 시점의 길은 제한 $S$ 를 지키고 같은 노드를 두 번 지나지 않으며, 길이는 매 단계에서 늘지 않았으므로 처음의 $Q$ 보다 길지 않다. ∎

경로 하나를 골라 가른다

이 절이 이 글에서 가장 촘촘하다. 하는 일은 하나다. $k$ 층의 한 칸을 내는 길을 하나 골라, 그 길이 $k$ 번 노드를 밟는지로 갈라 본다. 갈라진 두 경우가 그대로 점화식의 두 항이 된다.

$k \ge 1$ 을 잡고 $D^k[i][j]$ 를 $D^{k-1}$ 로 나타내 본다.

길이 아예 없는 경우. $\{1,\dots,k\}$ 아래에서 $i$ 부터 $j$ 까지 가는 길이 하나도 없는 경우를 먼저 털어 둔다. 이때 $D^k[i][j]$ 는 $\infty$ 이고 나머지 두 값도 $\infty$ 다.

오른쪽 두 값이 $\infty$ 일 수밖에 없는 까닭은 이렇다. $D^{k-1}[i][j]$ 가 유한하면 그 길이 곧 $i \to j$ 길이고, $D^{k-1}[i][k] + D^{k-1}[k][j]$ 가 유한하면 두 조각을 $k$ 에서 이으면 되기 때문이다. 세 값이 모두 $\infty$ 이니 점화식은 그대로 성립한다.

아래에서는 길이 하나라도 있는 경우를 본다. 그 값을 실제로 내는 길이 있다는 것부터 확인해 둔다. 최솟값이라고 적어 두기만 하고 그 값을 내는 길이 실제로 없다면, 뒤에서 길 하나를 집어 드는 논증이 설 자리를 잃는다.

같은 노드를 두 번 지나지 않는 길은 노드를 겹치지 않게 늘어놓은 것이라 유한 개뿐이고, 길이 하나라도 있으면 정리 1로 바꾼 길이 그 안에 들어오니 비어 있지도 않다. 유한하고 비지 않은 모임에서는 최솟값이 반드시 달성된다.

남은 것은 이 최솟값이 겨루는 길 전체를 놓고 잰 값과 같다는 확인이다. 그 모임은 겨루는 길 전체의 일부이므로 전체를 놓고 잰 하한이 그 최솟값보다 크지 않고, 정리 1이 아무 길이나 그 모임 안의 길로 길이를 늘리지 않고 바꿔 주므로 작지도 않다. 두 값이 같으니 $D^k[i][j]$ 는 어떤 길이 실제로 내는 값이다.

최단 거리는 하나뿐이지만 그 거리를 내는 길은 여러 개일 수 있다. “그 최단 경로”라고 지목하면 있지도 않은 유일성을 슬쩍 빌려 쓰게 되니, 그런 길 중 아무거나 하나를 골라 $P$ 라 한다. 길 $P$ 의 길이는 $|P|$ 로 적는다.

정리 1을 $S = \{1,\dots,k\}$ 에 적용하면 $P$ 를 같은 노드를 두 번 지나지 않는 길로 바꿀 수 있고, 바꾼 길은 길이가 늘지 않았는데 최솟값 아래로 내려갈 수도 없으므로 여전히 최단이다. 처음부터 그런 $P$ 를 골랐다고 두어도 좋다. 이때 $|P| = D^k[i][j]$ 이고 $P$ 의 중간 노드는 모두 $\{1,\dots,k\}$ 안에 있다.

$P$ 는 $k$ 번 노드를 중간에 지나거나 지나지 않는다. 둘 중 하나이고 둘 다일 수는 없다. 이 갈림이 그대로 점화식의 두 항이 된다.

$k$ 를 지나지 않는 경우. $P$ 의 중간 노드는 $\{1,\dots,k\}$ 안에 있으면서 $k$ 가 아니므로 모두 $\{1,\dots,k-1\}$ 안에 있다. 곧 $P$ 는 $D^{k-1}[i][j]$ 를 겨루는 후보 중 하나다. $D^{k-1}[i][j]$ 는 그 후보 전체의 최솟값이므로

D^{k-1}[i][j] \le |P| = D^k[i][j]

이다.

$k$ 를 지나는 경우. $P$ 가 같은 노드를 두 번 지나지 않으므로 $k$ 는 $P$ 에 정확히 한 번 나온다. 자를 자리가 정해졌다. 그 자리에서 $P$ 를 앞 조각 $P_1: i \to k$ 와 뒤 조각 $P_2: k \to j$ 로 자른다.

두 조각의 중간 노드는 $P$ 의 중간 노드에서 $k$ 를 뺀 것이므로 모두 $\{1,\dots,k-1\}$ 안에 있다. $P_1$ 은 $D^{k-1}[i][k]$ 의 후보, $P_2$ 는 $D^{k-1}[k][j]$ 의 후보이고 각 값은 자기 후보 전체의 최솟값이므로

D^{k-1}[i][k] + D^{k-1}[k][j] \le |P_1| + |P_2| = |P| = D^k[i][j]

이다.

어느 경우에 들어가든 두 값 중 하나가 $D^k[i][j]$ 이하다. 곧 두 값의 최솟값도 $D^k[i][j]$ 이하다.

반대 방향. 여기까지는 한쪽 부등호만 얻었다. 두 값의 최솟값이 $D^k[i][j]$ 보다 작은 경우가 아직 열려 있어, 등호로 닫으려면 반대쪽도 세워야 한다.

부등호를 반대로 세우려면 $D^k[i][j]$ 쪽에 후보를 하나씩 대 주면 된다. 오른쪽 값이 $\infty$ 인 항은 부등식이 저절로 성립하니, 값이 유한해 그 값을 내는 길이 실제로 있는 경우만 보면 된다.

$\{1,\dots,k-1\}$ 만 쓰는 길은 $\{1,\dots,k\}$ 아래에서도 그대로 쓸 수 있다. 허용 집합이 넓어졌을 뿐 후보가 사라지지는 않으므로, $D^{k-1}[i][j]$ 를 내는 길은 $D^k[i][j]$ 의 후보이기도 하다. 곧 $D^k[i][j] \le D^{k-1}[i][j]$ 다.

$D^{k-1}[i][k]$ 를 내는 길과 $D^{k-1}[k][j]$ 를 내는 길을 $k$ 에서 이어 붙이면 $i$ 에서 $j$ 로 가는 길이 된다. 이어 붙인 길의 중간 노드는 두 조각의 중간 노드와 새로 중간이 된 $k$ 뿐이라 모두 $\{1,\dots,k\}$ 안에 있다.

이것 역시 $D^k[i][j]$ 의 후보이므로 $D^k[i][j] \le D^{k-1}[i][k] + D^{k-1}[k][j]$ 다.

양쪽을 합치면 등호가 닫힌다.

D^k[i][j] = \min\!\left(D^{k-1}[i][j],\ D^{k-1}[i][k] + D^{k-1}[k][j]\right)

읽는 법은 간단하다. $k$ 층의 한 칸을 얻으려고 $k-1$ 층에서 꺼내 보는 칸은 $D^{k-1}[i][j]$ , $D^{k-1}[i][k]$ , $D^{k-1}[k][j]$ 세 개뿐이다. 아래층이 다 채워져 있으면 윗층은 칸마다 두 값을 견주어 채운다.

유일성은 쓰지 않았다. 증명 어디에서도 최단 경로가 하나뿐이라고 가정하지 않았다. 여러 개면 아무거나 골랐고, 고른 것이 두 경우 중 어디로 들어가든 부등식은 그대로 성립했다. 반대 방향은 특정한 길을 지목하지 않고 후보가 존재한다는 사실만 썼다.

동점 확인. 위 그래프에서 $3-4$ 간선의 가중치만 $10$ 대신 $7$ 이었다고 해 보자. $k=2$ 에서 $3\to4$ 직행이 $7$ , $3\to1\to2\to4$ 가 $5+1+1=7$ 로 최단 경로가 둘이다.

어느 쪽을 골라도 답은 같다. 앞을 고르면 2번을 지나지 않으므로 첫째 경우로 가서 $D^1[3][4] = 7$ 을 얻고, 뒤를 고르면 둘째 경우로 가서 $D^1[3][2] + D^1[2][4] = 6+1 = 7$ 을 얻는다. 어느 쪽이든 $7$ 이고 $\min$ 이 둘 다 덮는다.

k를 지나지 않는 길과 지나는 길. 둘 중 짧은 쪽이 D^k[i][j]다.

의사코드

W[i][j]에는 입력 그래프의 간선 가중치를 담는다. 간선이 없으면 INF, i == j면 0이다.

INF는 「길이 없음」을 나타내는 표지다. 길이 없는 칸이 실제 길보다 짧아 보이면 min이 없는 길을 답으로 고르므로, INF는 답이 될 수 있는 어떤 거리보다도 커야 한다.

여기서 「어떤 거리」는 존재하는 모든 길이 아니라 최단 거리 다. 사이클을 계속 돌면 길의 길이는 얼마든지 커지므로 유한한 INF가 모든 길을 넘어설 수는 없다. 표에 담기는 값은 최단 거리뿐이고, 앞서 본 대로 비음수 가중치에서 최단 거리는 같은 노드를 두 번 지나지 않으므로 간선을 많아야 $N-1$ 개 쓴다. 가중치의 최댓값을 $W_{\max}$ 라 하면 어떤 최단 거리도 $(N-1)W_{\max}$ 를 넘지 않는다. INF를 이 값보다 크게 잡으면 된다.

두 조각을 이어 붙이는 자리에서는 한쪽이라도 INF면 덧셈을 건너뛴다. 이어지지 않는 조각은 애초에 후보가 아니라 값을 만들 이유가 없고, 덧셈이 일어나지 않으니 INF끼리 더해 자료형을 넘칠 일도 없다. 실제로 더해지는 두 값은 모두 최단 거리이므로 합은 $2(N-1)W_{\max}$ 아래에 머문다. INF와 이 합이 함께 자료형 안에 들어가도록 정하면 넘칠 일이 없다.

점화식이 $k$ 층을 읽을 때 $k-1$ 층만 보므로 층을 축으로 하나 더 두고 $k$ 를 가장 바깥에서 돌리면 정의가 그대로 코드가 된다.

// D[k][i][j] : i -> j 중 중간 노드가 모두 {1..k} 에 있는 길의 최단 거리
int D[n + 1][n + 1][n + 1];

void floydWarshall(int W[][n + 1], int n) {
    // 기저: 중간 노드를 하나도 못 쓴다
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            D[0][i][j] = W[i][j];

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                int viaK = INF;                       // 한쪽이라도 INF면 이어 붙일 수 없다
                if (D[k - 1][i][k] != INF && D[k - 1][k][j] != INF)
                    viaK = D[k - 1][i][k] + D[k - 1][k][j];
                D[k][i][j] = min(D[k - 1][i][j], viaK);
            }
}

세 겹 반복이 각각 $N$ 번 도니 시간은 $O(N^3)$ 이다. 안에 넣은 INF 검사는 한 번에 상수 시간이라 차수를 건드리지 않는다. 배열이 잡는 칸도 $O(N^3)$ 이다. 정렬된 자료구조도, 우선순위 큐도 없이 세 개의 for와 비교 몇 줄이 전부다.

눈금으로 돌아오면

앞에서 $O(M\log N)$ 과 $O(NM\log N)$ 사이라는 눈금을 세워 두고, 무엇을 기대하며 읽을지 정하는 데 쓰기로 했다. $O(N^3)$ 을 그 위에 올려 본다.

성긴 그래프에서는 눈금을 벗어난다. 간선이 대략 $N$ 개일 때 다익스트라 $N$ 번은 $O(N^2\log N)$ 인데 $O(N^3)$ 은 그보다 느리다. 눈금의 위쪽 끝을 넘는 것이고, 이 경우 새 알고리즘을 배울 이유가 없다는 뜻이다.

밀집 그래프에서는 눈금 안에 들어온다. 간선이 대략 $N^2$ 개일 때 다익스트라 $N$ 번이 $O(N^3\log N)$ 까지 올라가고 플로이드·워셜은 $O(N^3)$ 그대로다. 흥미로운 경우는 이쪽이다. 다만 밀집 그래프에서는 다익스트라 쪽 구현도 함께 달라지므로 비교는 이 한 줄로 끝나지 않는다. 그 이야기는 다음 글에서 이어 간다.

핵심 정리

$D^k[i][j]$ 는 $i$ 에서 $j$ 로 가되 중간에 거치는 노드가 모두 $\{1,\dots,k\}$ 안에 있는 길의 최단 거리다. 끝점 $i$ 와 $j$ 는 이 제한을 받지 않는다.
기저 $D^0[i][j]$ 는 간선 가중치 그대로다. 간선이 없으면 $\infty$ , $i=j$ 면 $0$ 이다.
길 하나를 골라 $k$ 를 지나는지로 가르면 $D^k[i][j] = \min(D^{k-1}[i][j],\ D^{k-1}[i][k] + D^{k-1}[k][j])$ 를 얻는다. 양방향 부등식으로 닫히며 최단 경로의 유일성은 쓰이지 않는다.
정리 1이 이 논증을 떠받친다. 가중치가 비음수라서 사이클을 잘라낼 수 있고, 그래야 $k$ 가 한 번만 나와 자르는 자리가 정해진다.
$k=N$ 이면 제한이 사라지므로 $D^N$ 이 답이다. 세 겹 반복으로 $O(N^3)$ 에 채운다.

이어지는 글

의사코드는 $D$ 를 층까지 갖춘 3차원 배열로 잡아 $O(N^3)$ 칸을 쓴다. $k$ 층을 계산할 때 읽는 값은 $k-1$ 층뿐인데 지나간 층을 전부 들고 있어야 할 이유가 있을까. 플로이드·워셜의 메모리 줄이기에서는 이 배열을 두 층으로, 다시 한 층으로 줄이면서 덮어쓰기가 답을 망가뜨리지 않는 이유를 따진다.