최단 경로 탐색을 제대로 비교하기: Dijkstra·양방향 Dijkstra·A*

이 글의 아이디어 출처는 Instagram의 최단 경로 탐색 비교 포스트입니다. 원본 지도·영상·캡션·코드 자산은 사용하지 않았습니다. 아래 보드와 본문은 1차 논문과 권위 문서를 바탕으로 전제, 종료 조건, 반례를 독립적으로 다시 구성했습니다.

먼저 결론

Dijkstra, 양방향 Dijkstra, A*는 같은 race의 세 선수가 아니다. 알고 있는 정보와 유지해야 할 증명 조건이 다르다.

• Dijkstra는 모든 edge weight가 0 이상일 때 출발점에서의 최단 거리를 확정한다.
• 양방향 Dijkstra는 출발점과 도착점 양쪽에서 같은 원리를 적용하되, 첫 만남이 아니라 두 frontier의 lower bound가 현재 최선 경로를 이길 수 없을 때 멈춘다.
• A*는 목적지까지의 남은 비용을 추정하는 heuristic으로 탐색 순서를 바꾼다. 최적성을 유지하려면 heuristic의 성질과 closed node 재개방 정책이 맞아야 한다.

작은 지도에서 어느 색이 먼저 목적지에 닿는지만 보고 보편적인 승자를 고를 수 없다.

보드는 동일한 graph에서 탐색 순서와 frontier 차이를 관찰하는 도구다. 세 선택 모두 최종적으로 비용 10인 S → B → D → G → T를 찾지만, 확장한 정점과 도달 순서는 다르다. 애니메이션의 frame 수는 wall-clock benchmark가 아니며, 아래 복잡도와 종료 증명을 대신하지 않는다.

문제 계약: 무엇을 알고 무엇을 구하는가

graph를 G=(V,E), edge 비용을 w(u,v), 출발점을 s, 목적지를 t라고 하자. 이 글의 세 알고리즘은 기본적으로 다음을 전제로 한다.

1. 모든 edge 비용은 0 이상이다.
2. 합산 비용이 overflow하거나 NaN이 되지 않는다.
3. directed graph에서는 뒤쪽 탐색을 위해 원 graph의 edge 방향을 뒤집은 reverse graph를 정확히 만들 수 있다.
4. 실제 path가 필요하면 거리뿐 아니라 predecessor 또는 successor도 기록한다.

음수 edge가 있으면 “한 번 확정한 거리는 다시 줄지 않는다”는 Dijkstra의 핵심 증명이 깨진다. 음수 cycle이 없다면 Bellman–Ford나 Johnson처럼 그 조건을 다루는 알고리즘을 선택해야 한다.

Dijkstra: 가장 작은 tentative distance를 확정한다

Dijkstra의 1959년 논문은 한 node에서 다른 node까지 최소 길이 path를 구성하는 방법을 제시했다. 현대적인 priority queue 구현은 다음 상태를 유지한다.

• dist[v]: 지금까지 발견한 s→v 비용의 최솟값
• min-priority queue: 아직 확정하지 않은 후보를 tentative distance 순으로 보관
• prev[v]: 최적 path를 복원할 직전 node

가장 작은 key의 u를 꺼냈을 때 dist[u]가 확정되는 이유는 모든 edge가 비음수이기 때문이다. 아직 꺼내지 않은 node를 거쳐 u로 돌아오는 다른 path는 현재 minimum보다 더 싸질 수 없다.

정확한 종료 조건

목적지 t 하나만 필요하면 t가 priority queue에서 minimum으로 pop되어 확정될 때 멈출 수 있다. t가 처음 발견되거나 queue에 처음 들어갔을 때 멈추면 안 된다. 나중에 더 싼 path가 발견될 수 있다.

decrease-key 대신 같은 node의 새 후보를 queue에 다시 넣는 구현에서는 stale entry가 생긴다. pop한 distance가 현재 dist[u]와 다르면 건너뛰어야 한다. 그렇지 않으면 정답이 틀리지 않더라도 불필요한 relaxation과 잘못된 성능 관측이 생긴다.

복잡도

adjacency list와 binary heap이면 시간은 O((V+E) log V), 연결 graph에서 흔히 O(E log V)로 쓴다. graph와 queue·거리·predecessor를 포함한 공간은 O(V+E)다. adjacency matrix에서 매번 minimum을 선형 탐색하는 구현은 O(V²)가 될 수 있다. “Dijkstra의 속도”라는 말에는 graph 표현과 queue 구현이 빠져서는 안 된다.

양방향 Dijkstra: 첫 만남이 정답은 아니다

양방향 탐색은 s에서 forward search, t에서 backward search를 수행한다. directed graph의 backward search는 원 graph에서 incoming edge를 따라야 하므로 G가 아니라 reverse graph Gᴿ 위에서 실행한다.

다음 값을 유지한다.

• forward와 backward의 거리 distF, distB
• 두 priority queue의 minimum key minF, minB
• 지금까지 발견한 완전한 s→t path의 최선 비용 μ

두 방향이 같은 node를 보았거나 한 방향이 완화하는 edge의 반대쪽 비용을 다른 방향이 알고 있으면 μ 후보를 갱신할 수 있다. 하지만 처음 겹친 node에서 즉시 종료하면 틀릴 수 있다. 먼저 만난 연결이 전체 비용이 가장 작은 연결이라는 보장이 없기 때문이다.

bidirectional Dijkstra의 종료 조건을 분석한 논문이 강조하듯 구현 변형에 맞는 stopping condition이 필요하다. 표준적인 비음수 가중치 쌍방향 구현의 핵심 lower-bound 검사는 다음 형태다.

minF + minB ≥ μ

두 queue에서 앞으로 만들 수 있는 미완성 path의 비용 하한이 이미 찾은 μ보다 작지 않다면 더 싼 path는 남아 있지 않다. 그때 μ를 만든 meeting vertex 또는 crossing edge를 기준으로 forward predecessor와 backward successor를 합쳐 path를 복원한다.

양쪽에서 번갈아 한 번씩 확장하는 것이 항상 균형 잡힌 전략은 아니다. queue minimum이 더 작은 쪽, frontier 크기, edge 비용 분포를 고려할 수 있지만, expansion 정책을 바꾸면 종료 증명과 μ 갱신이 여전히 맞는지 함께 검토해야 한다.

언제 실제로 줄어드는가

branching factor가 b이고 해의 깊이가 d인 균일한 unweighted tree에서는 한쪽의 O(b^d) 대신 양쪽에서 대략 O(b^(d/2))씩 보는 직관이 있다. 이것은 weighted graph의 보편적 시간 보장이 아니다.

• t에 incoming edge가 매우 많거나 reverse graph가 훨씬 조밀하면 backward frontier가 커질 수 있다.
• s와 t가 가깝거나 graph가 작으면 두 queue와 두 거리표의 overhead가 더 크다.
• one-way 구조와 비용 분포가 불균형하면 한쪽 탐색이 거의 전체 graph를 볼 수 있다.
• worst-case asymptotic bound는 여전히 Dijkstra와 같은 O((V+E) log V) 범주다.

공간도 두 방향의 거리·queue·path 복원 정보를 유지하므로 O(V+E)이고, 상수 비용은 커질 수 있다.

A*: g와 h를 합쳐 목적지 쪽을 먼저 본다

Hart, Nilsson, Raphael의 A* 원 논문은 heuristic 정보를 사용해 minimum-cost path 탐색을 지시하는 방법을 다뤘다. Nils Nilsson의 Stanford bibliography에서도 원 논문의 서지 정보를 확인할 수 있다.

A*는 queue priority를 다음처럼 둔다.

f(n) = g(n) + h(n)

• g(n)은 s에서 n까지 지금까지 발견한 실제 비용이다.
• h(n)은 n에서 t까지 남은 비용의 추정치다.
• h(n)=0이면 A*의 순서는 Dijkstra와 같다.

admissible과 consistent를 구분한다

heuristic이 admissible하다는 것은 실제 남은 최단 비용 h*(n)을 넘지 않는다는 뜻이다.

0 ≤ h(n) ≤ h*(n)

consistent 또는 monotone이라는 것은 모든 edge (u,v)에 대해 다음 triangle inequality를 만족한다는 뜻이다.

h(u) ≤ w(u,v) + h(v)

consistent heuristic은 path를 따라 f가 감소하지 않게 하며, 표준 graph-search A*에서 한 번 확정한 node를 다시 열지 않아도 되는 근거가 된다. admissible이지만 inconsistent한 heuristic도 올바른 reopen을 허용하면 최적 path를 찾을 수 있지만, closed node를 영구히 막는 구현은 틀릴 수 있다.

NetworkX의 astar_path 문서는 heuristic이 overestimate하면 결과가 shortest path가 아닐 수 있다고 경고하며, 같은 node의 heuristic 값을 cache해 runtime 중 갱신하는 설계를 지원하지 않는다고 명시한다. library를 쓸 때도 admissibility뿐 아니라 API의 caching·weight·hidden edge 계약을 읽어야 한다.

보드의 A*는 화면 좌표의 Euclidean distance를 그대로 쓰지 않는다. 각 edge에 대해 weight / geometricLength의 최솟값을 scale로 정하고, h(n) = scale × euclidean(n,t)를 사용한다. 그러면 모든 edge에서 h(u) ≤ w(u,v) + h(v)가 성립하므로 이 고정 graph에서는 consistent한 lower bound가 된다. 좌표만 보고 실제 edge 비용과 같다고 가정하지 않고, 먼저 weight에 맞춰 휴리스틱을 제한한 것이다.

정확한 종료 조건

consistent heuristic을 사용하는 표준 graph search에서는 t가 minimum f로 pop될 때 종료할 수 있다. admissible하지만 inconsistent하다면 더 좋은 g를 발견한 closed node를 reopen하는 구현이 필요하다. “t를 처음 발견했을 때” 종료하는 것은 Dijkstra와 마찬가지로 안전하지 않다.

복잡도

consistent heuristic으로 각 node를 한 번만 확정하는 표준 graph-search를 명시적으로 저장된 finite graph, binary heap, adjacency list에 적용하면 O((V+E) log V) 시간과 O(V+E) 공간 범주로 볼 수 있다. admissible하지만 inconsistent한 heuristic 때문에 node를 reopen하면 같은 node와 edge를 여러 번 처리할 수 있어 이 단순 bound를 그대로 적용할 수 없다. 좋은 heuristic은 실제 확장 수를 크게 줄일 수 있지만 asymptotic guarantee를 자동으로 바꾸지 않는다.

implicit search tree에서는 heuristic 오차에 따라 확장 수가 지수적으로 커질 수 있고, A*는 frontier와 closed set을 memory에 보존해 공간이 먼저 병목이 되기도 한다. heuristic 계산 자체가 비싸면 확장 수 감소가 wall-clock 개선으로 이어지지 않을 수 있다.

애니메이션 속도가 보편 성능 결론이 아닌 이유

시각화 한 장은 correctness와 performance의 일부만 보여준다.

• frame duration과 한 frame당 expansion 수는 임의의 UI 설정이다.
• node 좌표가 있어도 edge weight가 거리와 같은지는 별도 계약이다.
• tie-breaking 순서만 바뀌어도 같은 비용의 path와 색칠 영역이 달라진다.
• graph 크기, branching, obstacle, directedness와 weight 분포가 결과를 바꾼다.
• A*는 heuristic quality와 계산 비용, Dijkstra는 priority queue, 양방향 탐색은 reverse adjacency 구축 비용에 영향을 받는다.
• warm cache, allocation, language runtime과 path reconstruction을 포함했는지도 benchmark마다 다르다.

따라서 보드는 “왜 frontier가 다르게 자라는가?”를 묻는 도구이고, “A*는 언제나 몇 배 빠르다”를 증명하는 benchmark가 아니다.

세 가지 반례

1. 음수 edge에서 Dijkstra가 깨진다

s→a 비용 2, s→b 비용 5, b→a 비용 -10이라고 하자. a를 비용 2로 먼저 확정한 뒤 b를 거치면 -5가 되므로 settled distance가 줄어든다. 비음수 전제가 없으면 증명이 무너진다.

2. 첫 frontier 만남은 최적 meeting이 아닐 수 있다

한 방향이 edge 수가 적지만 비싼 corridor에서 먼저 다른 방향과 만날 수 있고, 조금 늦게 만나는 다른 corridor의 총비용이 더 작을 수 있다. 그래서 μ를 계속 갱신하고 minF + minB ≥ μ를 확인해야 한다.

3. overestimate 또는 reopen 누락이 A*를 틀리게 한다

s→a→t 비용이 2+2=4, s→b→t 비용이 1+5=6일 때 h(a)=10, h(b)=0으로 두면 a를 과대평가한 A*가 비용 6의 t를 먼저 pop해 반환할 수 있다.

더 미묘하게, admissible하지만 inconsistent한 heuristic에서 a를 먼저 closed 처리한 뒤 b를 통해 더 싼 a 경로를 발견할 수 있다. closed node를 reopen하지 않으면 suboptimal path가 남는다. admissible이라는 말만 확인하고 구현 정책을 보지 않으면 안 되는 이유다.

선택표

알고리즘 이름보다 query 형태, update 빈도, memory 한도, path가 필요한지 여부가 선택을 결정한다.

테스트 전략

공통 correctness oracle

작은 random graph에서는 Floyd–Warshall 또는 조건에 맞는 Bellman–Ford 결과와 비교한다. 세 구현 모두 같은 graph와 weight type, overflow 정책을 사용해야 한다.

Dijkstra

• s=t이면 거리 0과 길이 1의 path
• disconnected t는 unreachable
• zero-weight edge와 같은 비용의 여러 path
• stale priority-queue entry 건너뛰기
• 음수 edge 입력 거부
• 거리만 필요한 실행과 path 복원 실행의 일치

양방향 Dijkstra

• undirected graph와 directed reverse graph를 각각 검증
• 최적 연결이 meeting vertex가 아니라 crossing edge에서 생기는 경우
• 첫 만남의 비용이 최적이 아닌 반례
• minF + minB = μ 경계에서 안전한 종료
• 한쪽 frontier가 훨씬 큰 비대칭 graph
• path가 없을 때 두 queue 종료와 복원 실패 처리

A*

• h=0 결과와 Dijkstra 결과가 항상 일치
• grid의 Manhattan distance처럼 consistent한 heuristic
• admissible하지만 inconsistent한 heuristic에서 reopen on/off 비교
• overestimate heuristic이 suboptimal 결과를 만드는 명시적 반례
• 같은 f의 tie-breaking이 비용은 유지하면서 path 모양만 바꾸는지 확인
• heuristic 호출 비용과 cache 정책을 포함한 benchmark

performance test에서는 정답 확인 뒤에 expanded node 수, relaxation 수, maximum frontier, peak memory, heuristic 호출 수, reverse graph 구축 시간과 wall-clock을 함께 기록한다. 하나의 숫자만 보면 원인을 설명할 수 없다.

권위 출처와 provenance의 역할

• Dijkstra의 1959년 원 논문 PDF
• A* 원 논문 DOI
• Nils Nilsson의 Stanford publication bibliography
• NetworkX A* API와 admissibility 경고
• bidirectional Dijkstra의 first-meet 오류와 stopping condition 분석

Instagram 링크는 질문을 발견한 provenance다. 알고리즘의 전제와 정확성은 논문, 구현 계약, 반례와 test가 뒷받침한다.

마지막 원칙

최단 경로 알고리즘은 “어느 색이 더 빨리 도착했는가”로 선택하지 않는다. 확정해도 되는 거리의 조건, 아직 남은 path의 lower bound, heuristic이 약속하는 범위를 먼저 적는다. 그 증명이 구현의 종료조건과 일치하는지 확인한 뒤, 실제 graph 분포에서 확장 수와 전체 비용을 측정해야 한다.