에듀테크 프로젝트 대시보드
벨만-포드 알고리즘 (Bellman-Ford)
다익스트라는 빠르지만 음수 가중치 간선이 하나라도 있으면 답이 틀릴 수 있다
(한 번 확정한 노드를 다시 줄일 수 없기 때문). 벨만-포드는 훨씬 단순한 발상으로 이 문제를 푼다 —
모든 간선을 쭉 훑으며 완화(relax)하는 작업을 정점 수 − 1 번 반복한다.
최단 경로는 간선을 최대 V−1 개만 지나므로, 매 라운드마다 최소 한 정점씩 정답이 확정되어
V−1 라운드면 모두 끝난다. 한 번 더 돌렸는데도 값이 줄면 음수 사이클이 있다는 신호다.
시간 복잡도는 O(V·E).
완화(relax)란 간선 u → v (가중치 w) 에 대해
dist[v] > dist[u] + w 이면 dist[v] = dist[u] + w 로 갱신하는 것이다.
A 를 출발점으로 하여, [다음 라운드] 를 누르며 거리표가 어떻게 채워지는지 관찰해 보자.
점선 간선은 음수 가중치다.
사이클이 없는 최단 경로는 같은 정점을 두 번 지나지 않으므로 간선을 최대 V−1 개 포함한다.
한 라운드에서 모든 간선을 훑으면, 출발점에서 간선 k개 거리에 있는 정점은 늦어도 k번째 라운드에
정답이 확정된다. 따라서 가장 먼 정점도 V−1 라운드 안에 확정된다.
V−1 번을 꽉 채워 돌리는 것이다. 실제로는 “이번 라운드에 갱신이 하나도 없으면 즉시 종료”
하는 최적화를 흔히 쓴다.
간선 가중치를 모두 더한 값이 음수인 사이클이 있으면, 그 사이클을 돌 때마다 거리가 계속 줄어들어
최단 경로가 −∞ 로 정의되지 않는다. 벨만-포드는 V−1 라운드를 끝낸 뒤
한 라운드를 더 돌려 본다. 정답이 확정됐다면 더 이상 줄어들 수 없어야 하는데,
여전히 완화되는 간선이 있다면 음수 사이클이 존재한다는 뜻이다.
위쪽 시뮬레이터에서 [예제: 음수 사이클] 을 고르면 B→C→D→B 의 가중치 합이 -1 이라
추가 라운드에서 계속 갱신이 일어나는 것을 볼 수 있다.
| 벨만-포드 | 다익스트라 | |
|---|---|---|
| 음수 간선 | 허용 ✔ | 불가 ✘ (틀린 답) |
| 음수 사이클 | 탐지 가능 ✔ | 탐지 못 함 |
| 시간 복잡도 | O(V·E) | O(E·log V) (힙) |
| 동작 방식 | 모든 간선을 V−1번 완화 | 가장 가까운 정점부터 확정(탐욕) |
| 쓰이는 곳 | RIP 라우팅, 환율 차익거래 탐지, SPFA | 지도 길찾기, 네트워크 OSPF |