다익스트라 알고리즘

다익스트라 알고리즘은 출발점 한 곳에서 다른 모든 곳까지 가장 짧은 길을 찾아 줍니다. 출발점에서 가까운 곳부터 하나씩 거리를 확정합니다. 그렇게 바깥으로 넓혀 갑니다. 길의 길이에 음수가 없어야 맞는 답이 나옵니다.

쉽고 빠른 이해

지도 위 한 지점에서 다른 모든 지점까지 가장 빨리 가는 길을 알려 줍니다. 교차로 다섯 개가 있는 동네에서 사무실 앞 교차로를 출발점으로 주면, 나머지 네 교차로까지 몇 분 걸리는지가 한꺼번에 나옵니다.

가능한 길을 전부 늘어놓고 견주면 교차로가 조금만 늘어도 길의 수가 감당 못 할 만큼 불어납니다. 도로 개수만 세는 방법은 오래 걸리는 도로와 금방 지나는 도로를 가리지 못합니다.

출발점의 거리를 0 으로 적고, 나머지는 아직 모른다는 뜻으로 무한대를 적습니다.
아직 확정하지 않은 곳 가운데 거리가 가장 작은 곳을 골라 확정합니다. 확정한 곳의 거리는 다시 고치지 않습니다.
방금 확정한 곳을 거쳐 가는 편이 더 짧은 이웃이 있으면 그 이웃의 거리를 고쳐 적습니다.
모든 곳이 확정될 때까지 2 와 3 을 되풀이합니다.

대가는 둘입니다. 길이가 음수인 도로가 있으면 틀린 답을 냅니다. 다음에 확정할 곳을 빨리 고르려면 가장 작은 값을 먼저 꺼내 주는 우선순위 큐라는 자료구조가 따로 필요합니다.

상세

이 절은 다익스트라 알고리즘이 무엇을 받아 무엇을 내는지부터 봅니다. 그다음 교차로 다섯 개짜리 작은 지도 하나로 절차를 끝까지 따라갑니다. 답이 왜 맞는지, 언제 틀리는지, 얼마나 걸리는지는 그 뒤에 차례로 봅니다.

이름은 이 절차를 처음 내놓은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에게서 왔습니다.

넣는 것과 나오는 것

다익스트라 알고리즘은 그래프 위에서 돕니다. 그래프는 점과 그 점들을 잇는 선으로 관계를 나타낸 구조입니다. 무엇과 무엇이 이어져 있는지를 담는 그릇입니다.

점을 노드라고 합니다. 정점이라고도 부릅니다. 점을 잇는 선은 간선이라고 합니다. 도로 지도라면 교차로가 노드, 도로가 간선입니다.

간선마다 숫자가 하나씩 붙습니다. 이 숫자가 가중치입니다. 가중치는 그 간선을 지나는 비용을 뜻합니다. 도로 지도에서는 그 도로를 지나는 데 걸리는 분이 가중치입니다. 가중치가 붙은 그래프를 가중 그래프라고 합니다.

한 길의 길이는 그 길이 지나는 간선들의 가중치를 모두 더한 값입니다. 앞으로 이 합을 거리라고 부릅니다. 두 노드 사이에서 거리가 가장 작은 길을 최단 경로라고 합니다.

넣는 것은 가중 그래프와 출발 노드 하나입니다. 나오는 것은 출발 노드에서 다른 모든 노드까지의 최단 거리입니다. 길 자체도 함께 얻을 수 있습니다. 그 방법은 아래 「길을 되짚는 법」에서 봅니다.

가중치에는 조건이 하나 붙습니다. 음수가 없어야 합니다. 걸리는 시간이나 거리처럼 비용을 나타내는 값은 음수가 되지 않으므로 대개 이 조건을 만족합니다. 왜 이 조건이 필요한지는 뒤에서 따로 봅니다.

예시로 쓸 교차로 지도

절차를 따라갈 작은 지도는 아래와 같습니다. 교차로는 A · B · C · D · E 다섯 개입니다. 도로는 모두 양방향입니다. 선 위의 숫자가 그 도로를 지나는 데 걸리는 분입니다.

flowchart TD
    A((A)) ---|4| B((B))
    A ---|1| C((C))
    C ---|2| B
    B ---|1| D((D))
    C ---|5| D
    D ---|3| E((E))

A 에서 B 로 바로 가면 4분입니다. C 를 거쳐 가면 1 더하기 2 로 3분이라 더 짧습니다. 돌아가는 길이 더 짧을 수 있다는 점이 이 문제를 까다롭게 만듭니다.

가능한 길을 모두 늘어놓고 견주는 방법도 있습니다. 교차로가 조금만 늘어도 길의 가짓수가 감당 못 할 만큼 불어납니다. 그래서 큰 지도에는 쓸 수 없습니다. 지나는 도로의 개수만 세는 방법은 4분짜리 도로 하나를 1분 · 2분짜리 도로 둘보다 짧다고 잘못 봅니다. 다익스트라 알고리즘은 이 두 문제를 함께 피합니다.

가까운 곳부터 확정하는 절차

이 소절은 A 를 출발점으로 두고 절차를 한 단계씩 따라갑니다. 절차가 쓰는 것은 거리 표 하나입니다.

거리 표는 노드마다 「지금까지 찾은 가장 짧은 거리」를 적어 두는 표입니다. 처음에는 출발점 A 만 0 이고 나머지는 모두 무한대입니다. 무한대는 그 노드로 가는 길을 아직 하나도 못 찾았다는 표시입니다.

절차는 한 단계마다 노드 하나를 확정합니다. 확정은 그 노드의 거리 표 값이 최종 답이라고 못 박는 일입니다. 한 번 확정한 노드의 값은 다시 고치지 않습니다.

한 단계는 두 동작으로 이루어집니다.

확정하지 않은 노드 가운데 거리 표 값이 가장 작은 노드를 골라 확정합니다.
방금 확정한 노드에 바로 붙은 이웃을 하나씩 봅니다. 그 노드를 거쳐 가는 편이 더 짧으면 이웃의 값을 더 작은 값으로 고쳐 적습니다.

2번 동작을 완화라고 부릅니다. 영어 relaxation 을 옮긴 말입니다. 이 동작이 있어야 돌아가는 길이 더 짧은 경우를 잡아냅니다.

아래 표는 앞의 지도에서 A 를 출발점으로 절차를 끝까지 돌린 것입니다. 한 줄이 한 단계입니다. 마지막 칸은 그 단계에서 완화로 고친 값입니다.

단계	확정한 노드	확정한 거리	완화로 고친 값
1	A	0	B: ∞ → 4 · C: ∞ → 1
2	C	1	B: 4 → 3 · D: ∞ → 6
3	B	3	D: 6 → 4
4	D	4	E: ∞ → 7
5	E	7	고칠 이웃 없음

2단계에서 B 의 값이 4 에서 3 으로 줄었습니다. C 를 거쳐 가는 길을 찾은 것입니다. 3단계에서는 D 가 6 에서 4 로 줄었습니다. C 에서 바로 가는 5분짜리 도로보다 B 를 거쳐 가는 쪽이 짧기 때문입니다.

확정된 순서는 A, C, B, D, E 입니다. 각 노드의 거리는 차례로 0, 1, 3, 4, 7 입니다. 거리가 작은 노드부터 차례로 확정됐습니다.

확정할 노드가 남지 않으면 절차가 끝납니다. 그때의 거리 표가 답입니다. 출발점에서 갈 수 없는 노드는 끝까지 무한대로 남습니다. 그 노드로 가는 길이 없다는 답입니다.

먼저 확정한 거리가 최종 답인 까닭

절차는 확정한 값을 다시 고치지 않습니다. 이 소절은 그래도 답이 틀리지 않는 까닭을 봅니다. 앞 표의 3단계, 곧 A 와 C 를 확정한 뒤 B 를 확정하는 순간을 예로 듭니다.

막 확정하려는 노드를 X 라고 부릅니다. 3단계에서는 값이 3 인 B 가 X 입니다. X 로 가는 어떤 길이든 출발점에서 시작하므로 처음에는 확정한 노드 위를 지납니다. 그 길을 따라가다 처음 만나는 확정 안 된 노드를 Y 라고 부릅니다. X 자신이 Y 일 수도 있습니다.

flowchart TD
    subgraph done["확정한 노드"]
        S(("출발점"))
        P(("Y 바로 앞 노드"))
    end
    S -->|"확정한 노드만 지남"| P
    P --> Y(("Y · 확정 안 됨"))
    Y -->|"남은 간선 · 음수 아님"| X(("X · 값이 가장 작음"))
    S -.->|"거리 표 값"| X

Y 바로 앞까지는 확정한 노드만 지납니다. 절차는 노드를 확정할 때마다 그 이웃을 완화했습니다. 그래서 Y 바로 앞 노드를 확정할 때 Y 로 들어가는 간선도 이미 완화됐습니다. 이 길로 Y 까지 가는 비용은 Y 의 거리 표 값보다 작을 수 없습니다.

그리고 Y 의 거리 표 값은 X 의 값 이상입니다. X 가 확정 안 된 노드 가운데 값이 가장 작기 때문입니다. Y 가 X 자신이면 두 값은 같습니다.

남은 것은 Y 에서 X 까지 가는 간선들입니다. 가중치가 음수가 아니면 간선을 더 지날수록 합은 커지거나 그대로입니다. 그래서 이 길의 비용은 X 의 값보다 작아질 수 없습니다. X 의 거리 표 값이 곧 최단 거리입니다.

3단계에 대어 보면 이렇습니다. B 로 가는 길이 A · C 밖으로 나가며 처음 만나는 노드는 B 자신이거나 D 입니다. B 자신이면 A 와 C 만 지난 길이고, 그중 가장 짧은 A → C → B 의 3 이 이미 표에 있습니다. D 라면 그때 D 의 값이 6 이라 D 에 닿는 데만 3 보다 많이 듭니다.

이 논리는 「앞으로 더할 값이 음수가 아니다」 한 가지에 기댑니다. 이 한 가지가 무너지면 절차 전체가 무너집니다.

매 단계에서 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 방식을 그리디 알고리즘이라고 합니다. 탐욕 알고리즘이라고도 부릅니다. 다익스트라 알고리즘은 이 방식으로 최적의 답을 보장하는 절차입니다.

음수 가중치에서 틀리는 까닭

음수 가중치가 하나만 있어도 답이 틀릴 수 있습니다. 노드 셋짜리 그래프로 봅니다.

이번에는 간선에 방향이 있어서 화살표 방향으로만 갈 수 있습니다. 이런 그래프를 방향 그래프라고 합니다. 양방향 도로에 음수를 붙이면 그 도로를 오가기만 해도 거리가 끝없이 줄어듭니다. 그런 경우와 섞이지 않게 한쪽 방향으로 둡니다.

flowchart TD
    A((A)) -->|2| B((B))
    A -->|3| C((C))
    C -->|"-2"| B

A 를 출발점으로 돌리면 첫 단계에서 B 에 2, C 에 3 이 적힙니다. 다음 단계에서 값이 더 작은 B 를 먼저 확정합니다. B 의 거리는 2 로 굳습니다.

그 뒤에 C 를 확정하면 C 를 거쳐 B 로 가는 길이 드러납니다. 3 에 -2 를 더해 1 입니다. 하지만 B 는 이미 확정돼서 고치지 않습니다. 절차의 답은 2 로 남습니다. 참 답은 1 입니다.

음수 가중치는 가중치가 비용이 아니라 이익이나 환급을 나타낼 때 생깁니다. 이런 그래프에는 벨만-포드 알고리즘을 씁니다. 벨만-포드는 확정 없이 모든 간선을 여러 번 되풀이해 완화합니다. 그래서 음수 가중치를 다루는 대신 더 오래 걸립니다.

우선순위 큐로 다음 노드 고르기

매 단계의 첫 동작은 값이 가장 작은 노드를 고르는 일입니다. 이 소절은 그 고르기에 드는 견줌을 줄이는 방법과 그 방법을 옮긴 코드를 봅니다.

가장 단순한 방법은 거리 표를 처음부터 끝까지 훑는 것입니다. 노드가 V 개면 한 번 고를 때마다 V 개를 견줍니다. 노드마다 한 번씩 고르므로 모두 합하면 V × V 번쯤 견줍니다.

견줌을 줄이는 방법은 우선순위 큐를 쓰는 것입니다. 우선순위 큐는 넣어 둔 값 가운데 가장 작은 것을 먼저 꺼내 주는 자료구조입니다. 거리 표를 훑는 대신 이 큐에서 하나를 꺼내면 다음 노드가 나옵니다.

우선순위 큐는 흔히 이진 힙으로 만듭니다. 이진 힙은 값을 나무 모양으로 매달아 가장 작은 값이 늘 맨 위에 오게 하는 구조입니다. 값을 넣거나 꺼낼 때는 맨 위에서 맨 아래로 이어지는 한 줄만 고쳐 놓으면 됩니다.

그 한 줄의 길이는 log V 쯤입니다. log V 는 V 를 1 이 될 때까지 반으로 나눈 횟수입니다. 노드가 백만 개여도 스무 번 남짓이라, 매번 V 개를 훑는 것보다 훨씬 적습니다. 그래서 이진 힙에서는 넣기와 꺼내기가 각각 log V 에 비례하는 시간에 끝납니다.

완화로 값이 줄면 그 노드를 새 값과 함께 큐에 한 번 더 넣습니다. 그러면 한 노드가 큐에 여러 번 들어 있을 수 있습니다. 꺼낸 노드가 이미 확정한 노드면 버리고 다음 것을 꺼냅니다.

아래는 앞의 교차로 지도를 파이썬으로 옮긴 것입니다. 노드마다 (이웃, 가중치) 목록을 달아 두었습니다. 그래프를 이렇게 담는 방식을 인접 리스트라고 합니다.

Python

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("C", 2), ("D", 1)],
    "C": [("A", 1), ("B", 2), ("D", 5)],
    "D": [("B", 1), ("C", 5), ("E", 3)],
    "E": [("D", 3)],
}

함수는 거리 표 dist, 확정한 노드 모음 done, 우선순위 큐 pq 셋을 씁니다. heapq 는 파이썬 리스트를 이진 힙으로 다루게 해 주는 표준 모듈입니다.

Python

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    done = set()
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in done:
            continue
        done.add(u)
        for v, w in graph[u]:
            if v in done:
                continue
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

heappop 은 큐에서 거리가 가장 작은 (거리, 노드) 쌍을 꺼냅니다. 꺼낸 노드가 done 에 이미 들어 있으면 건너뜁니다. 새로 확정한 노드의 이웃마다 완화를 합니다. 값이 줄면 그 이웃을 큐에 새로 넣습니다. 거리 표에 아직 없는 노드는 무한대로 칩니다.

이 함수를 앞의 지도에 돌리면 큐가 아래처럼 바뀝니다. 한 칸이 한 번 꺼낸 뒤의 모습입니다. 테두리가 점선인 두 칸은 이미 확정한 노드가 나와서 버린 꺼냄입니다.

flowchart TD
    K1["꺼냄 (0, A) · A 확정<br/>큐 (1, C) · (4, B)"]
    K2["꺼냄 (1, C) · C 확정<br/>큐 (3, B) · (4, B) · (6, D)"]
    K3["꺼냄 (3, B) · B 확정<br/>큐 (4, B) · (4, D) · (6, D)"]
    K4["꺼냄 (4, B) · 이미 확정이라 버림<br/>큐 (4, D) · (6, D)"]
    K5["꺼냄 (4, D) · D 확정<br/>큐 (6, D) · (7, E)"]
    K6["꺼냄 (6, D) · 이미 확정이라 버림<br/>큐 (7, E)"]
    K7["꺼냄 (7, E) · E 확정<br/>큐 비었음"]
    K1 --> K2 --> K3 --> K4 --> K5 --> K6 --> K7
    classDef drop stroke-width:3px,stroke-dasharray:5 5
    class K4,K6 drop

B 와 D 는 값이 줄 때마다 한 번 더 들어가서 큐에 두 번씩 있었습니다. 늦게 나온 쪽은 이미 확정한 뒤라 버립니다. 거리가 4 로 같은 (4, B) 와 (4, D) 는 튜플의 둘째 값을 견줘 B 가 먼저 나옵니다.

돌린 결과는 앞 표의 「확정한 거리」 칸과 같습니다.

Python

dist = dijkstra(graph, "A")
dist["B"]   # 3
dist["E"]   # 7

B 는 C 를 거쳐 3분, E 는 C · B · D 를 거쳐 7분입니다.

걸리는 시간

이 소절은 그래프가 커질 때 걸리는 시간이 어떻게 늘어나는지를 봅니다. 노드 수를 V, 간선 수를 E 로 적습니다.

이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지를 적는 약속입니다. O(V²) 는 노드가 두 배가 되면 비용이 네 배쯤 된다는 뜻입니다.

다음 노드를 고르는 방법에 따라 걸리는 시간이 갈립니다.

다음 노드를 고르는 방법	걸리는 시간	잘 맞는 그래프
거리 표를 매번 훑기	O(V²)	간선이 아주 많은 그래프
이진 힙 우선순위 큐	O((V + E) log V)	간선이 적은 그래프

힙 쪽의 시간은 큐를 다루는 횟수에서 나옵니다. 노드마다 확정할 때 한 번씩 꺼내므로 꺼내기에서 V log V 가 나옵니다. 간선 하나를 완화할 때마다 큐에 한 번 넣을 수 있으므로 넣기에서 E log V 가 나옵니다. 버리는 꺼내기는 넣은 횟수를 넘지 않아 이 몫에 들어갑니다.

출발점에서 모든 노드로 갈 수 있는 그래프라면 간선이 적어도 V − 1 개 있습니다. 그러면 E log V 가 V log V 를 덮습니다. 그래서 흔히 V 쪽을 떼고 O(E log V) 라고 줄여 적습니다.

간선이 노드 수의 제곱에 가까울 만큼 많으면 E log V 가 V² 보다 커집니다. 노드를 1000 개로 두고 간선 수만 늘려 가며 두 식에 수를 넣으면 아래와 같습니다. log V 가 10 쯤이라 힙 쪽 값은 간선 수의 열 배쯤입니다.

xychart-beta
    title "노드 1000 개일 때 두 식의 값"
    x-axis "간선 수" ["0", "5만", "10만", "15만", "20만", "25만", "30만", "35만", "40만", "45만", "50만"]
    y-axis "식의 값 (만)" 0 --> 500
    line [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
    line [0, 50, 100, 150, 200, 250, 300, 350, 400, 450, 500]

평평한 선이 거리 표를 훑는 쪽의 V² 입니다. 오르는 선이 힙 쪽의 E log V 입니다. 두 선은 간선이 10만 개쯤일 때 엇갈립니다. 그보다 간선이 많은 그래프에서는 거리 표를 훑는 쪽이 오히려 덜 걸립니다.

도로망처럼 한 노드에 이웃이 몇 개뿐인 그래프는 간선이 노드 수의 몇 배에 그칩니다. 그림의 왼쪽 끝보다도 훨씬 왼쪽이라 힙 쪽이 덜 걸립니다.

쓰는 메모리는 거리 표에 V 만큼, 큐에 많아야 E 만큼입니다.

길을 되짚는 법

거리 표만으로는 어느 길로 가야 하는지 모릅니다. 길을 얻으려면 완화로 값을 고칠 때마다 어느 노드를 거쳐 왔는지를 함께 적어 둡니다. 이 값을 직전 노드라고 부릅니다.

앞의 지도에서 직전 노드는 C 가 A, B 가 C, D 가 B, E 가 D 입니다. 목적지 E 에서 직전 노드를 거꾸로 따라가면 E, D, B, C, A 순서가 나옵니다. 이를 뒤집은 A → C → B → D → E 가 최단 경로입니다.

노드마다 직전 노드로 선을 그으면 출발점을 뿌리로 하는 나무 모양이 됩니다. 이 모양을 최단 경로 트리라고 합니다. 한 번 돌리면 모든 목적지까지의 길이 이 트리 하나에 담깁니다.

아래는 앞의 지도에 이 트리를 겹친 것입니다. 실선이 직전 노드를 잇는 선이고, 점선은 트리에 들지 않은 도로입니다. 노드 옆 숫자는 확정한 거리입니다.

flowchart TD
    A(("A · 0")) ---|1| C(("C · 1"))
    C ---|2| B(("B · 3"))
    B ---|1| D(("D · 4"))
    D ---|3| E(("E · 7"))
    A -.-|4| B
    C -.-|5| D

이 지도에서는 트리가 한 줄로 이어집니다. 한 노드가 여러 노드의 직전 노드가 되면 거기서 가지가 갈립니다.

쓸 때와 안 쓸 때

최단 경로를 구하는 절차는 여럿입니다. 아래 표를 위에서부터 차례로 물어, 처음 맞는 줄의 절차를 고릅니다.

상황	쓰는 절차
모든 노드 쌍 사이의 거리가 필요하다	플로이드 알고리즘
음수 가중치가 있다	벨만-포드 알고리즘
가중치가 모두 같거나 없다	너비 우선 탐색
목적지가 하나이고 남은 거리를 어림할 수 있다	[[A 스타 알고리즘
그 밖 — 가중치에 음수가 없고 출발점이 하나다	다익스트라 알고리즘

가중치가 모두 같으면 건넌 간선의 개수가 곧 거리입니다. 너비 우선 탐색은 우선순위 큐 없이, 먼저 넣은 것을 먼저 꺼내는 평범한 큐 하나로 같은 답을 냅니다. 그래서 더 싸게 끝납니다.

목적지가 하나뿐이면 다익스트라 알고리즘은 목적지를 확정하는 순간 멈춰도 됩니다. 그래도 거기까지 가는 동안 목적지와 반대쪽 노드까지 가까운 순서대로 훑습니다. A* 알고리즘은 목적지까지 남은 거리를 어림한 값을 더해 목적지 쪽 노드를 먼저 꺼냅니다.