정의

벨만-포드 알고리즘은 한 출발점에서 다른 모든 정점까지의 최단 거리를 구합니다. 다익스트라와 달리 음수 가중치 간선도 처리할 수 있으며, 음수 사이클도 감지합니다.

핵심 특성

• ✓음수 가중치 처리: 음수 간선이 있어도 최단 경로를 정확히 계산합니다.
• ✓V-1번 반복: 모든 간선을 V-1번 완화(relaxation)하면 최단 경로가 확정됩니다.
• ✓음수 사이클 감지: V번째 반복에서 갱신이 발생하면 음수 사이클이 존재합니다.

시간 복잡도