yeolyi.com성열의 컴퓨터공학

모든 쌍 최단 경로

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

지도 앱이 도시 사이 거리표를 만들려면 모든 출발점과 도착점 쌍의 거리가 필요합니다. 전기차의 배터리 소모량을 가중치로 보면 내리막에서는 충전이 되니 음수 간선도 생깁니다. 다익스트라 알고리즘은 출발점 하나에서의 거리만 구하고, 음수 간선이 있으면 확정한 정점에 나중에 더 짧은 길이 생겨 틀릴 수 있습니다.

모든 간선을 되풀이해 보기

음수 간선부터 해결해 봅시다. 출발점은 하나로 둡니다. 정점을 확정하는 대신, 간선 u→v마다 u를 거쳐 가는 거리가 표의 v보다 작으면 고칩니다. 이 일을 완화(relaxation)라 합니다. 이것을 모든 간선에 되풀이합니다.

몇 번이면 될까요? 최단 경로는 같은 정점을 두 번 지나지 않으니 간선이 많아야 V − 1개입니다. 모든 간선을 한 번씩 완화할 때마다 최단 경로의 앞에서부터 적어도 정점 하나가 더 맞는 거리를 얻으니, V − 1번이면 충분합니다. 이것이 벨만-포드 알고리즘(Bellman-Ford algorithm)이고, 간선이 E개면 O(VE)입니다.

완화 0번 / 4번
31−3426A0B∞C∞D∞
간선을 완화하는 순서
B→D 3D→A 1C→B −3A→B 4A→C 2C→D 6

출발점 A의 거리는 0, 나머지는 ∞입니다.

정점 옆 숫자가 A에서의 거리입니다. 끝까지 진행한 뒤 “D → A 가중치를 −3으로”를 켜고 다시 해 봅시다.

A→C→B→D→A를 한 바퀴 돌면 배터리가 1 늘어나니, 돌수록 거리가 줄어 최단 경로가 없습니다. 이처럼 가중치 합이 음수인 사이클을 음수 사이클(negative cycle)이라 합니다. V − 1번 뒤 한 번 더 완화했는데 표가 바뀌면 음수 사이클이 있습니다.

거쳐 갈 정점 늘리기

벨만-포드 알고리즘을 출발점마다 돌리면 모든 쌍을 구할 수 있지만 O(V²E)가 걸립니다. 표 한 장으로 한꺼번에 구해 봅시다.

i에서 j로 가는 거리를 i행 j열에 적습니다. 처음에는 간선 하나로 바로 가는 거리만 적습니다. 그다음 정점 k를 하나씩 골라 “k를 거쳐 가도 된다”고 허락하고, i에서 k를 거쳐 j로 가는 거리가 더 짧으면 고칩니다. 그러면 표에는 늘 지금까지 허락한 정점만 거쳐 가는 길 중 가장 짧은 거리가 적힙니다.

거쳐 가도 되는 정점: 없음
31−3426ABCD
출발 \ 도착ABCD
A042∞
B∞0∞3
C∞−306
D1∞∞0

간선 하나로 바로 가는 거리만 적었습니다. 간선이 없으면 ∞입니다.

옅은 칸은 지금 정점 k를 거치는 길의 앞뒤 조각이고, 하이라이트된 칸은 이번에 짧아진 칸입니다.

새 표는 k를 거치지 않는 길(앞 표의 값)과 k를 거치는 길(앞 표의 두 조각의 합) 중 짧은 쪽이니, 앞 표만 있으면 됩니다. 동적 계획법입니다. 이것이 플로이드-워셜 알고리즘(Floyd-Warshall algorithm)입니다.

1#include <stdio.h>
2
3int main(void) {
4 // 아직 길을 모른다
5 int INF = 1000000;
6 // A, B, C, D 사이의 거리.
7 // 처음엔 간선 하나로 바로 가는 거리만
8 int d[4][4] = {
9 {0, 4, 2, INF},
10 {INF, 0, INF, 3},
11 {INF, -3, 0, 6},
12 {1, INF, INF, 0},
13 };
14 // 거쳐 가도 되는 정점에 k를 더한다
15 for (int k = 0; k < 4; k++) {
16 for (int i = 0; i < 4; i++) {
17 for (int j = 0; j < 4; j++) {
18 if (d[i][k] < INF && d[k][j] < INF &&
19 d[i][k] + d[k][j] < d[i][j]) {
20 d[i][j] = d[i][k] + d[k][j];
21 }
22 }
23 }
24 }
25 for (int i = 0; i < 4; i++) {
26 printf("%d %d %d %d\n", d[i][0],
27 d[i][1], d[i][2], d[i][3]);
28 }
29 return 0;
30}

변수 없음
출력 없음

그래프는 위 데모와 같고 정점 A, B, C, D가 0, 1, 2, 3번입니다. 재생하며 d의 칸이 줄어드는 모습을 봅시다.

반복문 세 겹이라 O(V³)이고, 음수 사이클만 없으면 음수 간선이 있어도 맞습니다.

도전 문제

아래 방향 그래프에 플로이드-워셜 알고리즘을 쓰되, 거쳐 가도 되는 정점을 C, E, B, D, A, F 순서로 하나씩 더합니다. 표의 A→F 칸은 처음에 10입니다. 이 칸이 처음으로 바뀌는 것은 몇 번째 정점을 더했을 때일까요? 숫자로 답하세요.

A → B 1, B → C 1, C → D 1, D → E 1, E → F 1
A → F 10, A → D 4