[Algorithm] 다익스트라 알고리즘 : 음수 간선이 있으면 안 되는 이유

인트로

[2021.11.15 오타 수정]

[2022.08.16 오류 수정]

다익스트라 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘이다. 단 가중치가 모두 양수라는 조건이 있다. 이러한 이유는 다익스트라 알고리즘은 그리디(Greedy) 기반의 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 길을 찾기 때문에 음수 가중치는 고려하지 못한다.

반면 음수 가중치가 포함된 그래프라면 벨만-포드 알고리즘 사용 시 목표 노드까지의 최단 경로를 구할 수 있다. 

 

그렇다면 음수가 포함된 가중치에서 다익스트라 알고리즘을 사용하면 어떤 문제가 발생할까?

-
-
음수 가중치가 포함된 그래프에서 다익스트라 알고리즘의 문제점을 파악하면 벨만-포드 알고리즘을 더 쉽게 이해할 수 있을 것이다. 

 

다익스트라 문제점 : 음수 가중치

다익스트라 알고리즘의 분류는 그리디(Greedy) 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 최단거리를 계산할 수 있다는 논리를 기반으로 동작한다. 하지만 음수 가중치가 있다면 다익스트라 알고리즘에 모순이 생긴다. 글로 이해하기 어려우니 그림을 보며 이해하자.

 

아래와 같은 그래프가 있고 다익스트라 알고리즘에 기반해 A에서 C로 가는 최단거리를 구해보자.

1) 시작 노드 A를 제외한 모든 거리는 무한대이다.

Dist = { 0, ∞, ∞ }

 

다익스트라 계산법에 의해 Dist[A] + Cost[A, B] < Dist[B]를 만족하므로 Dist[B]를 갱신한다

Dist[B] = Dist[A] + cost[A, B]

Dist = { 0, 10, ∞ }

 

다익스트라 계산법에 의해 Dist[A] + Cost[A, C] < Dist[C]를 만족하므로 Dist[C]를 갱신한다.

Dist[C] = Dist[A] + cost[A, C]

Dist = { 0, 10, 4 }

 

2) 방문하지 않았으며 Dist 배열에서 가장 짧은 거리의 노드 C를 방문한다.

C를 방문했으니 더 이상 C의 거리가 갱신될 상황은 없으니 A에서 C까지의 거리는 4이다.

 

최종적으로 C까지의 최단거리는 -90이 아닌 4로 마무리된다.

이러한 문제로 음수 가중치가 포함된 그래프의 최단경로는 다익스트라 알고리즘으로 구할 수 없다.

 

다익스트라 알고리즘은 절대 음수 가중치를 계산못한다?

다익스트라 알고리즘은 항상 음수가 포함된 가중치 그래프의 최단경로를 계산하지 못할까?

정답은 "구할 수도 있고 못 구할 수도 있다."이다.

 

여기 다익스트라 알고리즘을 구현하는 세 가지 방법이 있다. 구현 방법에 따라 음수 가중치를 계산할 수도 못할 수도 있다.

 

Version 1 

Using a nested for-loop to relax vertices. This is the easiest way to implement Dijkstra's algorithm. The time complexity is O(V^2).

▶ 중첩 반복문을 사용한 간선 업데이트 구현 방식이다. 우선순위 큐를 사용하지 않는 방식으로 가장 가까운 거리의 노드를 찾고 해당 노드와 연결된 노드들의 최단거리를 갱신한다.

 

Version 2

Priority-queue/heap based implementation + NO re-entrance allowed, where re-entrance means a relaxed vertex can be pushed into the priority-queue again to be relaxed again later.

▶ 우선순위 큐를 사용하되 한 번 방문했던 노드는 절대 다시 방문하지 않는다. 즉 방문한 노드는 우선순위 재삽입하지 않는다. 

 

Version 3

Priority-queue/heap based implementation + re-entrance allowed.

▶ 2번과 유사하지만 한 번 방문한 노드를 다시 우선순위 큐에 삽입하는 것이 가능하다.

 

Version 1 & 2는 음수 가중치가 포함된 그래프의 최단거리를 계산하지 못한다. 반면 Version 3의 경우 노드의 재방문이 허용되므로 음수 가중치에 대한 최단거리를 계산할 수 있다.

 

여기서 알아둬야할 사실은 Version 3과 같이 방문했던 노드를 재방문 하는 것은 굉장히 오버헤드가 크며 노드의 재방문은 전통적인 다익스트라 알고리즘에 부합하지 않는다. 노드의 재방문은 벨만-포드 알고리즘과 더 유사하다고 볼 수 있다. 

유명한 개발자 동빈나님의 다익스트라 알고리즘 포스팅을 보면 우선순위 큐를 사용한 코드가 있다. 해당 코드가 Version 3와 같이 노드를 재방문하여 최단거리를 갱신하는 코드로 음수 가중치가 존재해도 최단 경로 갱신이 가능하다.

 

[참고]

전통적인 다익스트라 알고리즘은 방문한 노드를 다시는 재방문하지 않는다. 다익스트라 알고리즘이 그리디 기반의 알고리즘임을 기억하자.

참고 자료

https://stackoverflow.com/questions/42448373/dijkstra-with-negative-edges-dont-understand-the-examples-they-work-according

 

https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm