다익스트라: 최단 경로 찾기

간선(edge)마다 길이, 곧 가중치(weight)가 다른 그래프에서, 출발 정점(vertex) 하나부터 다른 모든 정점까지 최단 경로(shortest path)를 찾는 방법입니다. 「다음」을 눌러 가장 가까운 정점부터 하나씩 확정되는 모습을 따라가 보세요.

한 줄 답. 다익스트라는 확정 안 된 정점 가운데 지금까지 가장 가까운 정점을 하나 확정하고, 그 이웃까지의 거리를 더 짧으면 고치는 일(완화, relaxation)을 모든 정점이 확정될 때까지 되풀이합니다. 가중치가 모두 0 이상이면, 가장 가까운 정점은 다른 정점을 거쳐 돌아와도 더 짧아질 수 없어서 확정해도 됩니다. 가장 가까운 정점을 빨리 꺼내려고 힙을 쓰면, 간선이 E 개이고 정점이 V 개일 때 가장 나쁠 때도 E log V 에 비례하는 시간이 듭니다.

정점ABCDEF

「다음」을 누르면 한 걸음씩 나아갑니다. 걸음은 모두 25 개입니다. 정점 하나를 확정하는 걸음, 그 정점에서 나가는 간선마다 한 걸음, 끝에 길을 거슬러 가는 걸음 하나입니다. 초록으로 채운 정점은 확정한 정점이고 걸음이 지나도 초록으로 남습니다. 주황 고리는 지금 정점, 주황 화살표는 지금 보는 간선과 그 셈, 회색 화살표는 이미 확정한 정점으로 가는 간선(건너뜀)입니다. 줄을 그은 숫자는 고치기 전 거리입니다. 굵은 초록 간선은 지금 「바로 앞 정점」으로 이어진 간선이고, 끝까지 가면 최단 경로 트리가 됩니다. 표의 주황 칸은 이번 걸음에 고친 값입니다. 끝 걸음에는 고른 도착 정점에서 출발로 거슬러 가는 파란 화살표가 나옵니다. 그래프는 지어낸 것이고, 간선은 양쪽으로 다닐 수 있습니다.

해 볼 것. ① 걸음 2 에서 B 는 A 에서 바로 가는 간선으로 거리 4 가 됩니다. 걸음 4 에서 C(거리 2)를 확정하고, 걸음 6 에서 C → B 간선을 보면 B 가 3(C 를 거쳐 2 + 1)으로 줄어듭니다. 바로 가는 간선이 늘 가장 짧은 것은 아닙니다. ② D 는 ∞ → 10 → 8, E 는 ∞ → 12 → 10, F 는 ∞ → 14 → 13 으로 줄어듭니다. ③ 끝 걸음(25)까지 가면 A → F 의 최단 경로는 A → C → B → D → E → F, 길이 13 입니다. 도착 정점을 E 로 바꾸면 A → C → B → D → E, 길이 10 입니다.

1. 문제: 간선마다 가중치가 다를 때

정점(점)과 간선(선)으로 된 그림을 그래프라고 합니다. 간선마다 길이가 적혀 있고, 출발 정점 하나에서 다른 모든 정점까지 최단 경로를 찾고 싶습니다. 길의 길이는 지나는 간선 가중치의 합입니다.

가중치가 모두 같으면 지나는 간선 수만 세면 되니 너비 우선 탐색으로 풀립니다. 길이가 다르면 간선 수가 적은 길이 더 길 수 있습니다. 실험에서 A → B 는 간선 하나(4)지만 A → C → B 는 간선 둘로 3 입니다.

답은 정점마다 둘을 적습니다. 지금까지 아는 가장 짧은 거리와, 그 길에서 바로 앞 정점(선행 정점, predecessor)입니다. 바로 앞 정점을 도착에서 출발까지 거슬러 따라가면 길 전체가 나옵니다.

2. 생각: 가까운 것부터 확정한다

모든 길을 다 따져 보면 정점이 늘 때 길의 수가 매우 빨리 늘어납니다. 다익스트라는 이렇게 합니다.

  1. 출발 정점의 거리를 0, 나머지를 ∞(아직 모름)로 둡니다.
  2. 확정 안 된 정점 가운데 거리가 가장 작은 정점 u 를 골라 확정합니다.
  3. u 에서 나가는 간선마다, u 를 거쳐 가는 길이 더 짧으면 그 이웃 v 의 거리와 바로 앞 정점(u)을 고칩니다.
  4. 확정 안 된 정점이 없거나, 남은 정점의 거리가 모두 ∞ 일 때까지 2 ~ 3 을 되풀이합니다.

3 의 고치기를 식으로 적으면 이렇습니다. 책에서는 완화(relaxation)라고 부릅니다(출처).

dist[v] = min(dist[v], dist[u] + w(u, v))
전 5 B D 거리 3 · 확정 거리 10 바로 앞 C 후: B → D 간선을 봄 3 + 5 = 8 B D 거리 3 · 확정 거리 10 → 8 8 < 10 → 고침 바로 앞 B
완화: 간선 하나를 보고 고치기. 아래 「손으로 따라가기」 표의 3 걸음(실험의 걸음 12)입니다. 확정한 B 의 거리 3 에 간선 B–D 의 길이 5 를 더하면 8 입니다. D 가 알던 10 보다 작으니 D 의 거리를 8 로, 바로 앞 정점을 B 로 고칩니다. 위 식으로는 min(10, 3 + 5) = 8.

왜 확정해도 되나. 확정 안 된 정점 가운데 u 의 거리 d 가 가장 작다고 합시다. 출발에서 u 로 가는 다른 길이 있다면, 그 길은 확정 안 된 정점 하나(x)를 처음으로 지납니다. x 앞은 모두 확정한 정점이라 그 간선으로 이미 x 의 거리를 고쳐 두었으니, 그 길로 x 까지의 길이는 x 의 거리 이상이고, x 의 거리는 d 이상입니다. x 에서 u 까지 남은 가중치는 0 이상이라 합은 d 보다 작아질 수 없습니다. 그래서 u 의 거리는 이제 바뀌지 않습니다. 이 논리는 「가중치가 0 이상」에 기대고 있습니다.

성질뜻
확정한 거리는 다시 바뀌지 않는다가중치가 모두 0 이상일 때만. 그래서 도착 정점 하나만 필요하면 그 정점을 확정할 때 멈춰도 된다
출발 하나에서 모든 정점까지 한 번에 구한다정점마다의 거리와 바로 앞 정점이 같이 나온다
바로 앞 정점을 이으면 트리가 된다출발에서 모든 정점으로 가는 최단 경로가 트리 하나에 담긴다. 실험의 초록 간선
음수 길이가 있으면 틀릴 수 있다4절

3. 손으로 따라가기

실험 ① 의 그래프를 표로 끝까지 따라갑니다. 칸의 숫자는 지금까지 아는 거리, 괄호는 바로 앞 정점, ✓ 는 확정, 굵은 글자는 그 걸음에 고친 값입니다. 표의 한 걸음은 실험에서 정점 하나를 확정하는 걸음과 그 정점의 간선을 하나씩 보는 걸음들을 묶은 것입니다.

걸음확정ABCDEF왜
처음−0∞∞∞∞∞출발까지는 0. 다른 정점으로 가는 길은 아직 모름
1A (0)✓ 04 (A)2 (A)∞∞∞가장 가까운 정점 A(0). B: 0 + 4 = 4 < ∞, C: 0 + 2 = 2 < ∞
2C (2)✓ 03 (C)✓ 210 (C)12 (C)∞가장 가까운 정점 C(2). B: 2 + 1 = 3 < 4, D: 2 + 8 = 10 < ∞, E: 2 + 10 = 12 < ∞
3B (3)✓ 0✓ 3✓ 28 (B)12 (C)∞가장 가까운 정점 B(3). D: 3 + 5 = 8 < 10
4D (8)✓ 0✓ 3✓ 2✓ 810 (D)14 (D)가장 가까운 정점 D(8). E: 8 + 2 = 10 < 12, F: 8 + 6 = 14 < ∞
5E (10)✓ 0✓ 3✓ 2✓ 8✓ 1013 (E)가장 가까운 정점 E(10). F: 10 + 3 = 13 < 14
6F (13)✓ 0✓ 3✓ 2✓ 8✓ 10✓ 13남은 정점 F(13). 이웃이 모두 확정이라 고칠 것 없음

3 걸음에서 B 를 확정할 때 D 는 C 를 거친 10 에서 B 를 거친 3 + 5 = 8 로 줄어듭니다. 끝난 뒤 F 에서 바로 앞 정점을 거슬러 가면 F ← E ← D ← B ← C ← A. 뒤집으면 A → C → B → D → E → F, 길이 2 + 1 + 5 + 2 + 3 = 13 입니다.

4. 음수 길이에서 틀리는 까닭

가중치가 음수일 수 있으면, 나중에 확정할 정점을 거쳐 돌아오는 길이 더 짧을 수 있습니다. 2절의 「남은 가중치는 0 이상」이 깨지기 때문입니다. 아래 그래프는 한쪽으로만 가는 간선(화살표) 넷이고, B → A 가 −3 입니다. 양쪽으로 다니는 간선이 음수면 그 간선을 오가기만 해도 길이가 끝없이 줄어 최단 경로가 없으니, 이 예는 한쪽으로만 가는 간선으로 둡니다.

정점다익스트라의 답진짜 가장 짧은 거리맞나

「진짜 가장 짧은 거리」는 S 에서 시작하는 모든 길을 다 따져 보는 함수로 구했습니다. 정점이 4 개라 다 따져 볼 수 있습니다. 주황 간선이 음수 간선입니다.

해 볼 것. 다익스트라는 S(0) → A(2) → C(3) → B(4) 차례로 확정합니다. 진짜 가장 짧은 거리는 A 가 1(S → B → A: 4 − 3), C 가 2(S → B → A → C)입니다. A 를 거리 2 로 확정할 때는 아직 확정 안 된 B(4)를 거쳐 오는 길이 더 짧아질 줄 몰랐습니다. 「확정한 거리는 다시 바뀌지 않는다」가 깨졌고, A 를 거쳐 가는 C 도 같이 틀렸습니다.

출처의 책은 다익스트라에 두 판이 있다고 적습니다. 정점 하나를 우선순위 큐에 한 번만 넣는 판(이 쪽의 실험과 코드처럼 확정한 정점을 다시 보지 않는 판)은 E log V 시간이 보장되지만 음수 간선에서 틀릴 수 있습니다. 여러 번 넣을 수 있게 한 판은 음수 사이클만 없으면 맞지만, 가장 나쁠 때 걸리는 시간이 지수로 늘어납니다. 그래서 책의 코드는 음수 간선을 받으면 오류를 냅니다. 음수 간선이 있으면 벨만-포드를 씁니다(6절).

5. 가장 가까운 것을 빨리 꺼내기: 힙

걸음마다 「확정 안 된 정점 가운데 거리가 가장 작은 것」을 찾아야 합니다. 정점이 V 개일 때 걸음마다 전부 훑으면 걸음이 V 번이라 훑는 일만 V × V 번입니다. 힙에 (거리, 정점) 을 넣어 두면 가장 작은 것이 늘 맨 앞에 있어 전부 훑지 않고 꺼냅니다. 출처의 책은 우선순위 큐를 쓴 다익스트라가 가장 나쁠 때 E log V 에 비례하는 시간과 V 에 비례하는 메모리를 쓴다고 적습니다.

쉬운 말로: 간선이 두 배면 시간도 두 배쯤 들고, 정점이 두 배가 되면 log V 가 1 커지는 만큼만 더 듭니다. Python 은 표준 라이브러리의 heapq 가 힙입니다. 가장 작은 것이 heap[0] 에 있고, heapq.heappop(heap) 한 줄이 그것을 꺼냅니다(출처).

import heapq
def dijkstra(graph, start):
    dist, prev, done = {start: 0}, {start: None}, set()
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)           # 확정 안 된 것 가운데 가장 가까운 것
        if u in done: continue               # 더 짧은 기록으로 이미 확정한 정점의 옛 기록
        done.add(u)                          # 확정
        for v, w in graph[u]:
            if v not in done and d + w < dist.get(v, float("inf")):
                dist[v], prev[v] = d + w, u  # 더 짧으면 고친다
                heapq.heappush(heap, (d + w, v))
    return dist, prev
graph = {"S": [("A", 2), ("B", 4)], "A": [("C", 1)], "B": [("A", -3)], "C": []}
print(dijkstra(graph, "S")[0])   # {'S': 0, 'A': 2, 'B': 4, 'C': 3}: 4절처럼 A 와 C 가 틀린다

이 코드는 거리가 줄 때마다 새 기록을 넣고, 옛 기록은 꺼낼 때 버립니다(if u in done). 그래서 힙에 간선 수만큼 기록이 쌓일 수 있어 메모리가 E 에 비례합니다. 실험 ① 의 그래프를 양쪽으로 넣으면 {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13} 가 나옵니다.

6. 언제 무엇을 쓰나

방법쓰는 경우걸리는 시간(가장 나쁠 때)더 드는 메모리좋은 점나쁜 점
너비 우선 탐색가중치가 모두 같을 때V + E 에 비례. 정점과 간선을 한 번씩 본다V큐 하나로 끝나 가장 단순하다길이가 다르면 틀린다
다익스트라(힙)길이가 다르고 모두 0 이상일 때E log V. 간선이 두 배면 두 배쯤V(위 코드처럼 힙에 여러 번 넣으면 E)빠르다. 도착 정점을 확정하면 멈출 수 있다음수 길이에서 틀릴 수 있다
벨만-포드음수 길이가 있을 때E × V. 정점과 간선이 모두 두 배면 네 배V음수 길이도 맞다느리다. 음수 사이클이 있으면 최단 경로가 없다

가장 좋을 때와 보통은 그래프 모양에 따라 달라 따로 적지 않았습니다. 다익스트라와 벨만-포드의 시간과 메모리는 출처의 책에 있는 값입니다.

어디에 쓰나

자주 묻는 것

도착 정점 하나만 알고 싶어도 끝까지 돌려야 하나요?

아닙니다. 도착 정점을 확정하는 순간 그 거리는 다시 바뀌지 않으니 거기서 멈춰도 됩니다. 실험에서 E 는 다섯째로 확정되고(거리 10), 그 뒤로 바뀌지 않습니다.

가중치가 모두 같으면 다익스트라를 써도 되나요?

맞는 답이 나옵니다. 다만 그때는 가까운 차례가 곧 지나는 간선 수의 차례라서, 힙 없이 큐 하나로 도는 너비 우선 탐색이 더 단순하고 빠릅니다.

음수 길이가 있으면 어떻게 하나요?

벨만-포드를 씁니다. 간선이 E 개, 정점이 V 개면 E × V 에 비례하는 시간이 들어 다익스트라보다 느리지만 음수 간선이 있어도 맞습니다. 다만 길이의 합이 음수인 사이클이 있으면 그 사이클을 돌수록 짧아져 최단 경로가 없습니다.

낱말

여기서 쓴 말책에서 부르는 말
점정점, 노드(vertex, node)
선간선(edge)
간선의 길이가중치(weight)
한쪽으로만 가는 간선으로 된 그래프방향 그래프, 유향 그래프(directed graph, digraph)
출발 하나에서 모든 정점까지 최단 경로단일 출발점 최단 경로(single-source shortest paths)
지금까지 아는 가장 짧은 거리거리 추정값(distTo[v], dist[v])
바로 앞 정점선행 정점, 직전 간선(predecessor, edgeTo[v])
더 짧으면 고치기완화(relaxation)
바로 앞 정점을 이은 트리최단 경로 트리(shortest-paths tree)
가장 작은 것을 빨리 꺼내는 자료 구조우선순위 큐(priority queue), 힙(heap)
길이의 합이 음수인 사이클음수 사이클(negative cycle)

출처

← 위상 정렬최소 신장 트리: 크루스칼·프림 →