알고리즘 8장
최단 경로: Bellman-Ford (음수 간선 대응)
Bellman-Ford는 모든 간선을 반복 완화해 음수 간선이 있어도 최단 거리를 찾고, 추가 완화로 음수 사이클을 감지합니다.
상태 변화
완화 라운드
round 1
S→A, A→B
round 2
B→C 갱신
extra
줄면 cycle
불변식
점검
V-1 라운드
최단 경로의 간선 수는 최대 V-1개라는 성질을 사용합니다.
전체 간선 완화
매 라운드 모든 간선 u→v를 검사합니다.
추가 라운드
V번째에도 줄어들면 음수 사이클을 의심합니다.
비용
시간복잡도는 O(VE)로 Dijkstra보다 무겁습니다.