yeolyi.com성열의 컴퓨터공학

최단 경로

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

내비게이션은 목적지까지 가장 짧은 길을 찾아 줍니다. 교차로를 정점, 도로를 간선으로 보면 너비 우선 탐색으로 간선이 가장 적은 길은 찾을 수 있습니다. 하지만 도로마다 길이가 다릅니다. 이처럼 간선마다 붙은 값을 가중치(weight)라 합니다.

간선 수와 길이

1023ABC

간선이 가장 적은 길: A → B 간선 1개, 길이 10

A에서 B로 바로 가면 간선은 하나지만 길이가 10이고, C를 거치면 간선은 둘이지만 길이는 5입니다.

지나는 간선의 가중치를 모두 더한 값이 가장 작은 길을 최단 경로(shortest path)라 합니다. 너비 우선 탐색은 가중치를 보지 않으니 이 문제를 풀지 못합니다. 가능한 길을 모두 나열하자니 정점이 조금만 늘어도 가짓수를 감당할 수 없습니다.

가장 가까운 정점부터 확정하기

너비 우선 탐색의 물결을 떠올려 봅시다. 물결이 일정한 속도로 간선을 따라 흐른다면, 간선 길이가 달라도 거리가 가까운 정점일수록 먼저 젖습니다. 이 순서를 그대로 따라가면 됩니다.

정점마다 지금까지 알아낸 거리를 적는 표를 둡니다. 출발점은 0, 나머지는 ∞(무한대)입니다.

  1. 아직 확정하지 않은 정점 중 표의 거리가 가장 작은 정점을 골라 확정한다.
  2. 그 정점의 이웃마다, 그 정점을 거쳐 가는 거리(그 정점의 거리 + 간선의 가중치)가 표의 값보다 작으면 표를 고치고 어디서 왔는지 적는다.
  3. 모든 정점을 확정하면 끝난다. 아니면 1로 돌아간다.

이 방법을 다익스트라 알고리즘(Dijkstra’s algorithm)이라 합니다. 매번 가장 가까운 정점을 고르니 그리디입니다.

412510162A0B∞C∞D∞E∞F∞

간선 위의 숫자를 누르면 가중치를 바꿀 수 있습니다.

정점ABCDEF
거리0∞∞∞∞∞
이전------

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

표의 흐린 값은 아직 확정하지 않은 거리입니다.

  1. 다음을 두 번 눌러 B의 거리를 봅시다.
  2. D–E 간선의 가중치를 10으로 올린 뒤 다시 해 봅시다.

C를 확정하면 B의 거리 4가 C를 거치는 3으로 고쳐집니다. 이처럼 흐린 값은 더 나은 길이 나타날 때마다 줄어들고, 한 번 진해지면 다시는 바뀌지 않습니다. 경로는 정점마다 적어 둔 이전 정점을 따라 거꾸로 올라가면 나옵니다.

위 1, 2단계를 C로 옮겨 봅시다.

1#include <stdio.h>
2
3int main(void) {
4 // A~F 사이 간선의 가중치. 0은 간선 없음
5 int graph[6][6] = {
6 {0, 4, 1, 0, 0, 0},
7 {4, 0, 2, 5, 0, 0},
8 {1, 2, 0, 0, 10, 0},
9 {0, 5, 0, 0, 1, 6},
10 {0, 0, 10, 1, 0, 2},
11 {0, 0, 0, 6, 2, 0},
12 };
13 // ∞ 대신 아주 큰 수
14 int INF = 1000000;
15 int dist[6] = {0, INF, INF, INF, INF, INF};
16 // 확정했으면 1
17 int done[6] = {0};
18 for (int n = 0; n < 6; n++) {
19 // 1. 확정하지 않은 정점 중
20 // 거리가 가장 작은 정점
21 int u = -1;
22 for (int v = 0; v < 6; v++) {
23 if (done[v] == 0 &&
24 (u == -1 || dist[v] < dist[u])) {
25 u = v;
26 }
27 }
28 done[u] = 1;
29 // 2. u를 거쳐 가는 거리가 더 작으면 고친다
30 for (int v = 0; v < 6; v++) {
31 int w = graph[u][v];
32 if (w > 0 && dist[u] + w < dist[v]) {
33 dist[v] = dist[u] + w;
34 }
35 }
36 }
37 for (int v = 0; v < 6; v++) {
38 printf("%c: %d\n", 'A' + v, dist[v]);
39 }
40 return 0;
41}

변수 없음
출력 없음

done에 1이 하나씩 늘 때마다 dist가 어떻게 고쳐지는지 봅시다.

확정해도 되는 이유

가장 작은 값을 고르자마자 확정해도 될까요? 확정하지 않은 다른 정점을 거쳐 오면 더 짧아질 수도 있지 않을까요?

그럴 수 없습니다. 다른 정점은 표의 거리가 지금 고른 정점보다 작지 않고, 거기서 간선을 더 지나도 짧아지지 않습니다. 이 논리는 가중치가 음수가 아니라는 데 기대니, 도로 길이처럼 음수가 될 수 없는 값에 다익스트라 알고리즘을 씁니다.

정점이 V개면 1단계를 V번 반복하고 매번 표를 훑으니 O(V²)입니다. 힙에 거리를 넣어 두면 가장 작은 값을 바로 꺼내 더 빠르게 만들 수 있습니다.

도전 문제

한쪽으로만 다닐 수 있는 간선 S→A 2, S→B 3, B→A w만 있는 그래프에서 S부터 다익스트라 알고리즘을 그대로 돌립니다. 이미 확정한 정점의 표는 다시 고치지 않습니다. 끝났을 때 표에 적힌 A의 거리가 실제 최단 거리와 달라지는 정수 w 가운데 가장 큰 값은 얼마일까요? 숫자로 답하세요.