모든 간선을 반복한다
출발점의 거리를 0으로 두고 도달 가능한 간선들을 통해 거리 후보를 줄인다. u까지의 후보와 u→v의 가중치를 더한 값이 v의 현재 후보보다 작으면 갱신한다. 이 간선 완화를 여러 차례 반복한다.
V−1회의 의미
도달 가능한 음수 순환의 영향을 받지 않는 최단 경로는 정점을 반복하지 않는 경로로 고를 수 있다. 정점이 V개라면 그런 경로의 간선 수는 최대 V−1개다. 이를 바탕으로 전체 간선을 V−1회 반복해 살피는 기본 구성을 얻는다.
음수 순환 검사
추가 반복에서도 도달 가능한 정점의 거리가 더 줄어들면 출발점에서 도달 가능한 음수 순환이 있음을 알 수 있다. 그래프의 어느 곳에든 음수 순환이 있다는 조건과 출발점에서 갈 수 있다는 조건은 구별한다.
다익스트라와 비교
표준 다익스트라는 음수 간선을 허용하지 않지만 벨만-포드는 음수 간선이 있어도 조건에 맞는 최단 거리를 구할 수 있다. 대신 기본 구현은 모든 간선을 반복해서 살피므로 큰 그래프에서 연산량이 많아질 수 있다.
관련 문서
다익스트라 알고리즘 / 최단 경로 / 가중 그래프 / 유향 그래프 / 간선 (그래프 이론) / 정점 (그래프 이론) / 시간 복잡도