다익스트라 알고리즘은 매우 빠르지만, 간선의 가중치가 음수인 경우에는 최단 경로를 보장하지 못한다는 치명적인 약점이 있습니다. 현실의 데이터 처리에서는 특정 경로 통과 시 보상을 받거나 비용이 차감되는 등 음수 가중치가 필요한 상황이 발생할 수 있습니다. 이때 해결책으로 제시되는 것이 바로 벨만-포드(Bellman-Ford) 알고리즘입니다. 본 가이드에서는 벨만-포드의 논리 구조와 음수 사이클 판별법을 명확히 정리해 드리겠습니다[cite: 410, 422].
1. 벨만-포드 알고리즘의 논리적 구조
[cite: 11, 33]
벨만-포드 알고리즘은 다익스트라처럼 '확정적'으로 나아가는 대신, 모든 간선을 매 라운드마다 확인하는 방식을 택합니다. 노드가 $V$개인 그래프에서 사이클이 없다면 최단 경로는 최대 $V-1$개의 간선으로 이루어진다는 원리에 기반합니다. 따라서 모든 간선에 대해 거리를 갱신하는 작업을 총 $V-1$번 반복하면 모든 노드까지의 최단 거리가 반드시 확정됩니다[cite: 237, 242, 288].
1-1. 최단 경로 갱신(Relaxation) 과정
각 라운드에서 모든 간선을 순회하며 다음의 조건을 검사합니다: `dist[next] > dist[now] + cost`. 만약 현재 노드를 거쳐서 다음 노드로 가는 비용이 기존에 알고 있던 비용보다 저렴하다면 테이블의 값을 업데이트합니다. 이 과정을 반복하면 점진적으로 실제 최단 거리에 수렴하게 됩니다.
2. 음수 사이클(Negative Cycle) 판별의 중요성
[cite: 11, 33]
벨만-포드 알고리즘의 가장 독보적인 장점은 음수 사이클의 존재 여부를 100% 감지할 수 있다는 점입니다. 음수 사이클이란 순환 경로를 돌 때마다 전체 가중치가 계속 줄어드는 무한 루프를 의미합니다. 만약 그래프에 음수 사이클이 존재한다면 최단 경로는 음의 무한대로 발산하게 되어 계산이 불가능해집니다[cite: 288].
2-1. 판별 방법: V번째 갱신 확인
$V-1$번의 반복이 끝난 후, 마지막으로 한 번 더(V번째) 모든 간선을 확인합니다. 이때 만약 거리가 또 줄어드는 노드가 발생한다면, 그 그래프에는 반드시 음수 사이클이 존재한다는 증거가 됩니다. 이는 시스템의 무한 루프 방지를 위해 필수적인 검증 절차입니다.
3. 다익스트라와의 성능 및 용도 비교
[cite: 11, 33]
벨만-포드는 음수 가중치를 처리할 수 있는 범용성을 갖춘 대신 성능 면에서는 다소 손해를 봅니다. 모든 라운드마다 모든 간선을 체크해야 하므로 시간 복잡도는 $O(VE)$입니다. 따라서 가중치가 모두 양수라면 속도가 빠른 다익스트라를, 음수 가중치가 섞여 있거나 사이클 판별이 필요하다면 벨만-포드를 선택하는 것이 공학적으로 최적의 판단입니다[cite: 288, 289].
1. 범용성: 다익스트라가 해결하지 못하는 음수 가중치 간선 상황에서도 최단 경로를 찾습니다.
2. 사이클 감지: $V$번째 갱신 시도를 통해 경로의 비용을 무한히 낮추는 음수 사이클을 판별합니다.
3. 복잡도: 시간 복잡도는 $O(VE)$이며, 안정적인 경로 탐색이 필요한 금융 서비스나 물류 스케줄링에 적합합니다.