벨만 포드 알고리즘은 음수 간선을 허용하는 단일 시작점 최단 경로 알고리즘이다. 도달 가능한 음수 사이클도 탐지할 수 있다.
원리
모든 간선에 대한 거리 완화를 반복한다. 정점 V개에서 단순 경로는 최대 V−1개 간선을 가지므로 그만큼의 단계가 기본 근거가 된다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
예시
어떤 경로의 간선 비용이 4와 −2이면 전체 비용은 2이다. 음수 간선이 있다는 이유만으로 최단 경로가 정의되지 않는 것은 아니다.
주의할 점
시작점에서 도달 가능한 음수 사이클을 반복하면 비용을 계속 낮출 수 있다. 일반적인 구현은 O(VE)이며 도달 불가능한 거리 표시에 덧셈하지 않도록 주의한다.