벨만 포드 알고리즘(Bellman-Ford Algorithm)

• Bellman-Ford Algorithm

시작점으로 부터 다른 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘과 유사합니다. 그러나 벨만 포드 알고리즘은 간선 cost가 음수인 경우에도 사용할 수가 있습니다. (O(VE)의 시간으로 다익스트라 알고리즘보다는 시간이 오래걸림)

 

 

 

위와 같은 그래프에서 0번 정점으로 부터 2번 정점까지의 최단거리를 구하고자 합니다.

최단거리는 0->1->2 를 거쳐서 12+(-9)=3이 됩니다. 그러나 다익스트라 알고리즘에서는 dist[1]=12 > dist[2]=7 이기 때문에 2번 정점을 방문하게 되고 따라서 음의 간선이 존재하는 그래프에서는 최단경로를 제대로 구할 수 없게 됩니다. 

 

벨만 포드 알고리즘은 2중 for문을 통해 가능한 모든 경우를 다 체크합니다.

최단경로라면 같은 정점을 두 번 이상 방문할 일이 없기 때문에 가능한 최단 경로의 간선 개수는 최대 V-1개 입니다.

따라서 루프를 V-1번 돌고, k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐 도달할 수 있는 최단 경로를 다 갱신해줘야합니다.

 

음의 가중치가 있는 그래프에서 최단경로를 구할 때 주의해야할 점이 있습니다.

최단거리를 구할 때 같은 정점을 두 번 이상 방문할 일이 없다고 했으나 위의 그래프에서 1->2->3->1을 순회하면 처음 1번 정점을 방문했을 때 보다 cost가 줄어듭니다. cycle이기 때문에 계속 돌면 cost가 무한히 줄어듭니다.

이렇게 가중치의 합이 0보다 작은 cycle을 음의 싸이클(negative cycle)이라고 합니다.

우선 루프를 V-1번 돌고 그 이상 돌아봐야 최단거리들이 갱신되지 않습니다.

그러나 음의 싸이클이 존재한다면 그 이후에 최단거리가 갱신되는 일이 발생합니다. 

따라서 음의 싸이클 존재여부를 알고싶다면, 마지막에 루프를 한 번 더 돌아서 최단거리가 갱신되는 일이 발생하는지 체크하면 됩니다.

---

• 관련 문제

https://www.acmicpc.net/problem/11657

11657번: 타임머신

• 문제 풀이

https://jioneprogstdy.tistory.com/33?category=1040034

BOJ 11657 타임머신

 

 

 

 

참고 : https://m.blog.naver.com/kks227/220796963742