[C++] 벨만-포드 알고리즘

핵심 요약

• 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용하는 알고리즘
• 음의 가중치가 있을 때 사용 → 음의 사이클을 찾음

 

동작 원리

1. 모든 간선들을 탐색하면서, 간선이 잇는 출발정점이 '한번이라도 계산 된 정점' 이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트 한다. ⇒ 방향성이 있기 때문!
2. 1번 과정을 반복한다. (N-1번)

 

음의 사이클을 찾는 방법

N-1번 반복 후, 1번 더 반복한다.

→ "정상적인 그래프라면, 즉, 음의 사이클이 발생하지 않는 그래프라면, N - 1번을 탐색한 이후에, 또 한번의 탐색을 더 하더라도 절대로! 최소비용이 변하는 정점이 발생하지 않는다"