다익스트라 알고리즘

수치해석 소프트웨어 마지막 수정: 2026-08-22 04:13:26

1. 개요[편집]

다익스트라 알고리즘 Dijkstra's algorithm
발표	Edsger W. Dijkstra (1959)
푸는 문제	단일 시작점 최단경로 (SSSP)
전제	간선 가중치 $w(u,v) \ge 0$
전략	라벨 설정(label-setting) — 그리디 확정
복잡도	이진힙 $O(E \log V)$, 피보나치힙 $O(E + V \log V)$
연속판	고속 행진법 (아이코날)

커피 한 잔 마시며 20분 만에 머릿속으로 만들었고, 종이도 연필도 없었다. — 다익스트라 본인의 회고

다익스트라 알고리즘(Dijkstra’s algorithm)은 간선 가중치가 음이 아닌 그래프에서 한 시작점으로부터 모든 정점까지의 최단경로를 구하는 그리디 알고리즘이다. 1959년 에츠허르 다익스트라가 두 쪽짜리 논문 하나로 발표했고¹, 그 뒤로 라우팅 프로토콜부터 경로 계획, 네트워크 흐름, 헝가리안 알고리즘의 내부 루프까지 최단경로가 필요한 거의 모든 자리에 박혀 버렸다.

이 위키의 맥락에서 다익스트라가 중요한 이유는 따로 있다. 이것이 “확정된 집합을 한 겹씩 넓혀 나간다”는 계산 패턴의 원형이고, 연속 영역에서 아이코날 방정식을 푸는 고속 행진법이 그 구조를 통째로 빌려 갔기 때문이다. 그래프와 PDE라는 전혀 다른 무대에서 같은 뼈대가 굴러가는데, 정확히 어디까지 같고 어디서 갈라지는지가 이 문서의 중심이다.

2. 알고리즘[편집]

각 정점 $v$ 에 잠정 거리 $d[v]$ 를 달아 두고( $d[s]=0$ , 나머지 $\infty$ ), 정점을 확정(settled) 과 미확정 으로 나눈다. 반복은 두 줄이다.

미확정 정점 중 $d$ 가 최소인 $u$ 를 꺼내 확정한다.
$u$ 의 각 이웃 $v$ 에 대해 $d[v] \leftarrow \min\big(d[v],\ d[u] + w(u,v)\big)$ 로 완화(relax) 한다.

끝. 확정된 값은 두 번 다시 건드리지 않으므로 정점 하나당 꺼내기가 정확히 한 번, 간선 하나당 완화가 정확히 한 번이다. 이렇게 “한 번 확정하면 끝”인 부류를 라벨 설정(label-setting) 알고리즘이라 부르고, 확정을 포기하고 수렴할 때까지 계속 완화하는 벨만-포드 알고리즘 같은 부류를 라벨 수정(label-correcting)이라 부른다.

3. 그리디가 통하는 이유 — 비음수 불변식[편집]

핵심 주장은 하나다. 꺼내는 순간 $d[u] = \delta(s,u)$ 다(여기서 $\delta$ 는 진짜 최단거리). 귀류법으로 보면 어디서 가정이 쓰이는지가 선명하다.

$d[u] > \delta(s,u)$ 인 채로 $u$ 가 꺼내졌다고 하자. 진짜 최단경로 $P: s \to u$ 를 잡고, $P$ 가 확정 집합을 처음 벗어나는 간선 을 $(x,y)$ 라 하자. $x$ 는 이미 확정이므로 $d[x]=\delta(s,x)$ 이고, $x$ 를 확정할 때 $(x,y)$ 를 완화했으니 $d[y] = \delta(s,y)$ 다. 그런데 $y$ 는 아직 큐 안에 있고 $u$ 가 최소로 뽑혔으므로 $d[u] \le d[y] = \delta(s,y)$ . 한편

\delta(s,u) = \delta(s,y) + \underbrace{\ell_P(y \to u)}_{\ \ge\ 0}\ \ge\ \delta(s,y)

여기서 $\ell_P(y \to u)$ 는 경로 $P$ 의 $y$ 이후 꼬리 부분의 길이다. 따라서 $d[u] \le \delta(s,u)$ 가 되어 가정과 모순이다. 부등호가 성립하는 유일한 근거가 밑줄 친 " $\ge 0$ " — 즉 뒤쪽 꼬리가 거리를 깎아 내리지 못한다는 사실이다. 이것이 비음수 가중치라는 전제의 전부다.

가중치에 음수가 하나만 섞여도 즉시 무너진다. $s \to a$ 가 1, $s \to b$ 가 2, $b \to a$ 가 $-2$ 인 세 점짜리 그래프에서 다익스트라는 $a$ 를 1로 확정해 버리지만 진짜 답은 0이다. 음수 간선이 있으면 $O(VE)$ 의 벨만-포드 알고리즘으로 가거나, 벨만-포드로 퍼텐셜 $\pi$ 를 한 번 구해 $w'(u,v) = w(u,v) - \pi(u) + \pi(v) \ge 0$ 으로 재가중한 뒤 다익스트라를 여러 번 돌리는 존슨(Johnson) 알고리즘을 쓴다. 음수 사이클이 있으면 애초에 최단경로가 정의되지 않는다.

4. 자료구조가 복잡도를 결정한다[편집]

알고리즘 자체는 고정이고, “미확정 중 최솟값 꺼내기”를 무엇으로 구현하느냐가 복잡도를 통째로 정한다. 즉 다익스트라의 복잡도표는 사실상 우선순위 큐의 복잡도표다.

큐 구현	꺼내기 $V$ 회	키 감소 $E$ 회	총합
배열 선형탐색	$O(V)$	$O(1)$	$O(V^2)$
이진 힙	$O(\log V)$	$O(\log V)$	$O(E \log V)$
$d$ -진 힙 ( $d = E/V$ )	$O(d \log_d V)$	$O(\log_d V)$	$O(E \log_{E/V} V)$
피보나치 힙	$O(\log V)$ 상각	$O(1)$ 상각	$O(E + V \log V)$

다익스트라의 원논문은 큐를 쓰지 않는 $O(V^2)$ 판이었고, 이건 조밀 그래프( $E \sim V^2$ )에서는 지금도 최선이다. 힙을 얹은 $O(E\log V)$ 판은 존슨(1977)에게서 왔다. 피보나치 힙(프레드먼·타잔 1984)이 키 감소를 상각 $O(1)$ 로 낮춰 이론적 최적 $O(E + V\log V)$ 를 찍었지만, 상수가 크고 캐시를 심하게 때려서 실측으로는 이진 힙이나 $d$ -진 힙이 이기는 경우가 많다. 실무 구현은 아예 키 감소를 포기하고 중복 삽입 후 낡은 항목을 꺼낼 때 버리는(lazy deletion) 방식을 쓴다 — 힙 크기가 $O(E)$ 로 늘지만 $O(E\log E) = O(E \log V)$ 로 같고, 역참조 배열을 관리할 필요가 없어 훨씬 단순하고 빠르다.²

5. A*·프림과의 관계[편집]

같은 뼈대에서 갈라져 나온 친척들이 있다.

A* 알고리즘: 목표까지 남은 비용의 추정치 $h$ 를 더한 $f = g + h$ 로 우선순위를 매긴다. $h$ 가 일관적(consistent, $h(u) \le w(u,v) + h(v)$ )이면 $w'(u,v) = w(u,v) - h(u) + h(v) \ge 0$ 이 되어, A*는 정확히 재가중된 그래프 위의 다익스트라다. 위에서 본 존슨 퍼텐셜과 같은 장치이고, $h \equiv 0$ 이면 다익스트라로 되돌아온다.
프림 최소신장트리: 코드가 다익스트라와 거의 글자 단위로 같다. 완화식만 $d[u] + w(u,v)$ 대신 $w(u,v)$ 로 바꾸면 최소 신장 트리가 나온다. 둘 다 “가장 싼 것부터 확정”이라는 그리디 알고리즘 패턴의 사례다.
값 반복·동적계획법: $\delta$ 가 만족하는 벨만 방정식 $\delta(v) = \min_u \{\delta(u) + w(u,v)\}$ 를 값이 작은 순서로 한 번에 확정하는 것이 다익스트라, 순서를 포기하고 수렴할 때까지 훑는 것이 값 반복이다. 동적 계획법의 최적성 원리가 정당성의 뿌리라는 점에서 둘은 형제다.

6. 격자와 메시 위에서 — 사라지지 않는 이방성 오차[편집]

여기서부터가 시뮬레이션 쪽 사람이 반드시 알아야 할 부분이다. 균일 격자를 그래프로 보고(이웃 4방향 또는 8방향, 간선 길이는 유클리드) 다익스트라를 돌리면 나오는 거리는 유클리드 거리가 아니다. 이동 방향이 유한 개의 벡터로 제한되므로, 격자 간격 $h \to 0$ 극한에서 얻어지는 것은 유클리드 노름이 아니라 허용 방향들의 볼록껍질을 단위구로 갖는 다각형 노름이다.

최악 오차는 인접한 두 허용 방향 사이의 각 간격 $\Delta$ 만으로 결정된다. 두 단위벡터를 잇는 현까지의 거리가 $\cos(\Delta/2)$ 이므로

\max_{\theta} \frac{d_{\text{격자}}}{d_{\text{유클리드}}} = \frac{1}{\cos(\Delta/2)}

이웃	각 간격 $\Delta$	최대 과대평가	최악 방향
4방향	$90^\circ$	$\sqrt{2} \approx 41.4\%$	$45^\circ$
8방향	$45^\circ$	$\approx 8.24\%$	$22.5^\circ$
16방향	$26.57^\circ$	$\approx 2.75\%$	$13.28^\circ$

핵심은 이 오차가 격자를 아무리 잘게 쪼개도 줄지 않는다는 것이다. $h$ 를 반으로 줄이면 경로가 잘게 톱니질 뿐 방향 집합은 그대로라, 상대오차는 위 표 그대로 남는다. 오차를 줄이려면 스텐실을 넓히는 수밖에 없고, 그러면 간선 수가 늘어 비용이 오른다. 격자 A* 경로가 계단처럼 보이고 사후에 경로 다듬기(string pulling)를 반드시 붙이는 이유가 이것이다.

고속 행진법이 갈라지는 지점이 정확히 여기다. FMM은 뼈대(최솟값 확정, 좁은 띠, 힙)를 통째로 다익스트라에서 가져오되, 완화식을 “이웃값 + 간선 길이의 최소”에서 상방향 이차방정식

(T-T_1)^2 + (T-T_2)^2 = (h/F)^2

의 큰 근으로 바꾼다. 두 축의 정보를 동시에 섞기 때문에 4점 스텐실만으로도 연속적인 진행 방향이 복원되고, $h \to 0$ 에서 참해로 수렴한다. 한 줄로 말하면 다익스트라는 일관적(consistent)이지 않고 FMM은 일관적이다. 자세한 비교는 고속 행진법 쪽이 본진이다.

삼각형 메시 위의 측지선에서도 같은 함정이 되풀이된다. 메시의 간선 그래프에 다익스트라를 돌리면 경로가 간선을 따라만 흐르므로, 메시를 아무리 세밀화해도 참 측지 거리로 수렴하지 않는다. 간선 위에 슈타이너 점을 흩뿌려 방향 집합을 늘리면 $(1+\varepsilon)$ 근사가 되고, 정확한 답을 원하면 미첼-마운트-파파디미트리우(1987)의 연속 다익스트라로 간다 — 정점 대신 “창(window)“이라는 구간 라벨을 거리 순서로 전파하는, 이름 그대로 다익스트라의 연속판이다.

7. 쓰이는 곳[편집]

라우팅: OSPF와 IS-IS의 최단경로 우선(SPF) 계산이 링크상태 데이터베이스 위의 다익스트라다. 인터넷 백본이 매일 이 알고리즘을 수천만 번 돌린다.
최소비용 유동: 네트워크 흐름의 연속 최단경로법은 잔여 그래프에 음수 간선이 생기는데, 존슨 퍼텐셜로 재가중해 다익스트라를 쓴다. 헝가리안 알고리즘의 최단 증가경로 판과 중국 우편배달부 문제의 홀수차 정점 매칭도 내부에서 다익스트라를 반복 호출한다.
경로 계획·게임: 경로 계획에서 목표가 여럿이거나 미리 모르는 경우(예: “가장 가까운 회복 아이템”)에는 휴리스틱을 못 쓰므로 A* 대신 다익스트라가 정답이다. 내비게이션 메시 위의 흐름장, 다이크스트라 맵(Dijkstra map) 기반 몬스터 AI가 그 예.
거리 변환·세그멘테이션: 비용이 균일하지 않은 거리 변환, 최소비용 경로 기반 영상 분할(intelligent scissors)이 전부 같은 루프다.

8. 여담[편집]

다익스트라는 이 알고리즘을 1956년 암스테르담의 카페 테라스에서 약혼자와 커피를 마시다 20분 만에 떠올렸다고 회고했다. 정작 논문으로 낸 건 3년 뒤였는데, 이유는 “당시엔 알고리즘을 발표하는 학술지가 거의 없었기 때문”. 같은 논문에 최소신장트리 알고리즘도 같이 실려 있다.
지도 앱의 경로 탐색은 겉보기와 달리 순수 다익스트라를 돌리지 않는다. 대륙 규모 도로망에서 매 질의마다 수억 개 정점을 확정할 수는 없으니, 전처리로 계층을 만들어 두는 축약 계층(contraction hierarchies)이나 허브 라벨링을 쓴다. 다익스트라는 그 전처리 안에서 부품으로 쓰인다.
2024년에는 적당한 힙을 붙인 다익스트라가 보편 최적(universally optimal) — 즉 어떤 그래프 위상에서든 그 위상에서 가능한 최선의 비교 기반 알고리즘과 상수 배 이내 — 임이 증명됐다.³ 65년 된 알고리즘이 아직도 정리를 낳고 있다.

9. 관련 문서[편집]

Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs”. Numerische Mathematik 1, 269–271. 제목의 겸손함(“a note”)과 본문 두 쪽 반이 이후 반세기 인용 수와 전혀 어울리지 않는다. 수치해석 저널에 실린 그래프 알고리즘이라는 점도 지금 기준으로는 묘하다. ↩
“키 감소 없는 게으른 다익스트라”는 알고리즘 수업에서 종종 편법 취급을 받지만, 실측에서는 거의 항상 이쪽이 빠르다. 캐시 지역성과 코드 단순함이 상각 복잡도 한 칸을 이기는 대표적 사례이고, 표준 라이브러리의 우선순위 큐에 키 감소 연산이 아예 없는 이유이기도 하다. ↩
Haeupler, Hladík, Rozhoň, Tarjan, Tětek (FOCS 2024), “Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps”. 정확히는 거리 순서로 정점을 나열하는 문제에 대한 보편 최적성이다. 다익스트라가 최적이라는 말이 “다른 알고리즘이 더 빠를 수 없다”가 아니라 “힙만 제대로 고르면 위상별 최적에 상수 배로 붙는다”라는 점에 주의. ↩