[그래프] 최단경로 2 (Bellman-Ford)

Bellman-Ford

- Dijkstra와 똑같은 Single Source Shortest Path (SSSP) 알고리즘

- 음의 간선있어도 작동

- Negative cycle detection 가능

- (최대) V-1번, E개의 edge 모두 relaxation : O(VE)

 

★ 반드시 1에서 출발하지 않아도? 
-> 벨만 포드에서 사이클을 찾는 방법을 생각해보시면 시작점은 큰 문제가 안된다는 것을 알 수 있습니다. 
1번으로 해도 되고 모든 점을 시작점으로 해도 상관 없을 것입니다

어차피 매번 edge 모두 relaxation -> 시작 지점은 중요하지 않음

 

* 참고 - relaxation = 최단 거리 업데이트

int relaxed;
if ((relaxed = D[e.from] + e.weight) < D[e.to]) {
  D[e.to] = relaxed;

 

Q. 왜 V-1번 돌려야 하는가?

To elaborate on why we do "V-1" iterations, it comes from the following lemma: "if the shortest path from the source to a node v ends with the edge u->v, and we already know the correct distance to u, and then we relax the edge u->v, we will find the correct distance to v". It is a pretty obvious lemma, if you think about it, but the correctness of Bellman-Ford, Dijkstra, and topological sort are all based on it.

The consequence of this lemma is that, in order to find the correct distance to a node v, we need to relax all the edges in the shortest path from the source to v *IN ORDER*.
Dijkstra and topological sort are efficient because we only relax the out-going edges from each node after we found the correct distance for that node, so we only need to relax the edges once.
Unfortunately, the combination of cycles and negative edges makes it impossible to find a "good" order to relax the edges. Thus, Bellman-Ford just relaxes all the edges in an arbitrary order (this is one iteration of Bellman-Ford).

In the first iteration, we find the correct distance for all the nodes whose shortest paths from the source have 1 edge. In the next iteration, we find the correct distances for all the nodes whose shortest paths from the source have 2 edges, and so on.
If the shortest path with the most edges has k edges, we need k iterations of Bellman Ford. Of course, we do not know what "k" is in advance, but, since shortest paths never repeat nodes (assuming there are no negative cycles), what we know for sure is that any shortest path will have at most V-1 edges (in the case where it goes through every node).
This is why V-1 iterations is ALWAYS enough, but often not necessary. If in one iteration of Bellman-Ford no relaxation yields any improvement, it means that we already found all shortest paths and we can finish.

 

아래 영상이 너무 설명을 잘해놨음.

특히, 최적화 코드 참고 (V-1 iteration다 하기 전에, 더 이상 relaxation 안일어나면, break)

https://youtu.be/lyw4FaxrwHg

 

최적화 코드

https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordEdgeList.java