다익스트라 알고리즘에 음수 가중치를 넣으면 왜 틀릴까

다익스트라 알고리즘의 핵심은 아직 확정하지 않은 정점 가운데 출발점에서 잠정 거리가 가장 짧은 정점을 골라 그 거리를 확정하는 데 있습니다. 1959년 원 논문도 최소 경로를 아는 정점의 집합에 정점을 거리가 작은 순서로 넣고, 목적지가 그 집합에 들어오면 답을 얻는 방식으로 설명합니다.

음수가 없을 때 탐욕적 선택이 안전한 이유

이 선택이 안전하려면 나중에 다른 정점을 거쳐 거리가 더 작아지는 일이 없어야 합니다. 모든 간선 가중치가 0 이상이면 아직 확정되지 않은 정점으로 돌아가는 경로에는 0 이상의 비용만 더해집니다. 그래서 지금 잠정 거리가 가장 작은 정점에 나중에 더 짧은 경로가 나타날 수 없습니다. 이 성질이 다익스트라의 탐욕적 선택을 지탱합니다.

간선 세 개로 만드는 반례

음수 간선이 하나만 있어도 이 논리가 깨집니다. 출발점 S에서 A로 가는 비용이 2, S에서 B로 가는 비용이 5, B에서 A로 가는 비용이 -4인 방향 그래프를 보겠습니다.

1959년 절차처럼 한 번 확정한 정점을 다시 고치지 않는 구현은 먼저 거리 2인 A를 확정합니다. 그러나 실제 최단 경로는 S→B→A이고 비용은 5+(-4)=1입니다. 처음에는 멀어 보이던 B를 거치자 이미 확정한 A의 거리가 줄어든 것입니다. 이 반례에는 음수 사이클이 필요하지 않습니다.

구현에 따라 결과가 다르다

그렇다고 “다익스트라는 음수 간선에서 언제나 오답을 낸다”고 말하면 정확하지 않습니다. Princeton의 Algorithms 교재는 정점이 우선순위 큐에 다시 들어갈 수 있는지에 따라 두 버전을 구분합니다. 재진입을 허용하는 버전은 음수 사이클이 없으면 정답을 찾지만 최악의 경우 실행 시간이 지수적으로 커질 수 있습니다. 한 번 확정한 정점을 다시 처리하지 않는 버전은 음수 간선에서 오답을 낼 수 있습니다. 같은 이름으로 불려도, 구현이 어떤 불변식과 보장에 기대는지가 결과를 가릅니다. 우선순위 큐로 흔히 쓰는 힙의 구조는 힙은 정렬된 배열이 아니다에서 다뤘습니다.

음수 간선이 있을 때 쓰는 알고리즘

음수 가중치가 있는 그래프에서 출발점 하나의 최단 경로를 구한다면 벨만–포드를 고려할 수 있습니다. 이 알고리즘은 출발점에서 도달할 수 있는 음수 사이클도 찾아내며, 정점 수를 V, 간선 수를 E라 할 때 최악의 경우 실행 시간은 VE에 비례합니다.

그래프가 DAG(방향 비순환 그래프)라면 음수 간선이 있어도 위상 순서대로 간선을 완화해 V+E에 비례하는 시간에 풀 수 있습니다.

도달 가능한 음수 사이클이 있으면 그 사이클을 반복해서 돌 때마다 경로 비용이 낮아집니다. 따라서 그 사이클을 거쳐 도달할 수 있는 목적지에는 유한한 최단 경로가 없습니다. 음수 간선이 있다는 사실만이 아니라, 음수 사이클이 출발점에서 도달 가능한지와 그래프가 DAG인지도 함께 확인해야 하는 이유입니다.

라이브러리 문서도 따로 확인한다

라이브러리 동작은 수학적 보장과 따로 확인해야 합니다. SciPy 문서는 scipy.sparse.csgraph.dijkstra의 입력을 음수가 아닌 거리로 정의하고, 음수 거리가 있으면 이 루틴이 동작하지 않으므로 Bellman–Ford나 Johnson 같은 알고리즘을 쓰라고 안내합니다(2026년 10월 4일 확인). 다른 라이브러리가 경고를 낼지, 예외를 던질지, 잘못된 결과를 돌려줄지는 쓰고 있는 버전의 문서를 확인해야 합니다.

참고한 문서

• E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs” (1959), CWI 보관 PDF
• Robert Sedgewick, Kevin Wayne, Algorithms 4.4 Shortest Paths (Princeton)
• SciPy: scipy.sparse.csgraph.dijkstra
• SciPy: scipy.sparse.csgraph.shortest_path

링크와 내용은 2026년 10월 4일에 확인했습니다. SciPy 문서는 버전에 따라 바뀔 수 있습니다.