벨먼-포드 알고리즘

 

최단 거리를 찾는 데에는 다익스트라가 가장 효율적이고 실생활에서도 많이 사용됩니다. 하지만, 만약 위 그림처럼 마이너스인 거리가 있다면? 오히려 돌아가는 게 이득인 거리가 있다면 다익스트라가 과연 제대로 동작할 수 있을까요? 

 

1. 다익스트라의 문제점

• 현재까지 가장 짧은 거리의 노드를 방문합니다. 
• 그 노드에서 이웃 노드로 가는 모든 경로를 "한 번만" 확인합니다.
• 이미 더 짧은 경로가 있다고 믿고, 그 뒤에 더 짧은 길이 나와도 무시합니다.
• 그렇기 때문에, E → C (-6)으로 돌아 가는게 이득이지만, 이미 확정을 지었기에 무시하게 됩니다.

즉, 다익스트라 알고리즘은 0 이상에서만 정상적으로 작동합니다. 음수는 제대로 계산할 수 없습니다.

 

2. 벨먼-포드 알고리즘 이란?

그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다익스트라 알고리즘과는 달리, 음수 가중치가 있는 간선도 처리할 수 있다는 것이 가장 큰 특징입니다. 그래프는 방향이 있어도 되고, 양방향 그래프여도 괜찮습니다.

 

3. 벨먼-포드 알고리즘 동작 원리

• 시작 정점을 제외한 모든 정점의 거리를 무한(INF)으로 초기화
• 노드수 -1 번 반복하면서 모든 간선(u → v)의 거리를 비교 후 갱신을 반복 합니다.  (if distance[u] + weight < distance [v]: 더 짧은 거리 발견 시 업데이트)
• 추가로 1번 더 모든 간선 확인 : 더 짧은 거리가 발견된다면 → 음수 사이클 존재 한다는 것을 확인 해야 합니다. 음수 사이클이 있다면, 무한 루프에 빠질 수 있어 주의가 필요합니다. 

4. 예제 코드 

 

 

5. 마무리

벨먼-포드 알고리즘은 범용성이 높은 알고리즘으로써 많은 곳에서 사용될 수 있습니다. 특히 음수가 존재하여, 무한 사이클이 발생하는지 여부를 확인하기가 좋습니다. 다만, 다익스트라 알고리즘에 비해 시간 복잡도가 조금 높다는 단점 또한 존재합니다.