Bellman-Ford's Algorithm

백준 11657번 '타임머신' : https://www.acmicpc.net/problem/11657

---

 

최단 경로를 계산하는 알고리즘의 한 종류이다. 간선의 가중치가 양수가 아니라 음수가 될 수 있다는 것만 제외하면, 일반적인 다익스트라 알고리즘과 같다.

 

 

음수 간선에 관한 최단 경로 문제는 다음과 같이 분류할 수 있다.

 

  1 .  모든 간선이 양수인 경우

  2 .  음수 간선이 있는 경우

           1) 음수 간선 순환은 없는 경우

           2) 음수 간선 순환이 있는 경우

 

음수 간선 순환이란, 순환하는 사이클이 존재하는데 사이클을 돌 때마다 간선의 값이 줄어드는 경우이다. 최단 경로를 찾고 싶은데 사이클을 돌 때마다 값이 줄어드므로 무한히 사이클을 돌게 되는 경우이다.

 

모든 음수 간선 순환이 문제가 되는 것은 아니다. 시작점에서 목적점까지의 최단 경로 사이에 음수 간선 순환이 존재할 때 문제가 되는 것이다.

 

따라서 음수 간선 순환을 회피할 수 있는 방법이 필요하다.

 

벨만 포드 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선 순환도 감지할 수 있다. 

벨만 포드 알고리즘의 기본 시간 복잡도는 정점의 개수 V개, 간선의 개수 E개일 때, O(VE)로 다익스트라 알고리즘에 비해 느리다.

 

 

참고
https://www.youtube.com/watch?v=PIT-aYPPPIQ