Bellman-Ford: 음수 가중치와 Negative Cycle 탐지

Bellman-Ford는 Single-Source Shortest Path를 계산하며 음수 Edge Weight를 지원합니다.

또한 Source에서 도달 가능한 Negative Cycle을 탐지할 수 있습니다.

Relaxation

Edge:

u → v, weight = w

에 대해:

dist[u] + w < dist[v]

이면 dist[v]를 갱신합니다.

모든 Edge를 최대 V-1번 반복해서 Relax합니다.

왜 V-1인가?

Negative Cycle이 없다면 Simple Shortest Path는 최대 V-1개의 Edge만 사용합니다.

Negative Cycle 탐지

V-1번 이후 한 번 더 Relaxation을 시도합니다.

여전히 값이 줄어들면 Source에서 도달 가능한 Negative Cycle이 존재합니다.

Dijkstra와 비교

Bellman-Ford:

• 음수 가중치 지원
• Negative Cycle 탐지
• O(VE)

Dijkstra:

• 일반적으로 non-negative weight
• 더 빠른 경우가 많음

활용

• Distance Vector Routing
• Difference Constraints
• Credit/Penalty Graph
• Negative Cycle Detection

Early Stop

한 Pass에서 아무 Update도 없다면 조기 종료할 수 있습니다.

복잡도

시간: O(VE)
공간: O(V)

정리

음수 Edge가 가능하거나 Negative Cycle 탐지가 필요할 때 Bellman-Ford가 중요한 선택지입니다.