CODEWITHSUNDEEP
algorithmgraphshortest-pathbellman-ford
hieppm
hieppm

Reputation: 113

Why need (node number - 1) iterations in Bellman Ford algorithm to find shortest paths?

enter image description here

Image: 4 iterations, with (a) is the original graph. (b), (c), (d), (e) correspond to result after each iteration. Example from "Introduction to Algorithm 3rd"

Hi, I do not understand few aspects about the algorithm. I hope someone could help. Below are my questions.

In each iteration, all edges are relaxed, as far as I concern. I expected all the node are updated distance in the first iteration. So why in the first iteration (b), only distance of node t and y are updated but the other still infinity?

Another question is, why need (node number - 1) iterations in which all edges are relaxed? What is guaranteed to achieve at each iteration so that the algorithm must run in (node number - 1) time to make sure the shortest path is found as long as no negative-weight cycles exist?

Upvotes: 5

Views: 4073

Answers (2)

Isaac_Zhu
Isaac_Zhu

Reputation: 105

Pure induction proof is convincing while hard to get. Most of the answers I saw are not easy to get because of the lack of an example.

In my opinion, if you have some basic knowledge in induction, the proof of correctness is simple enough to understand. Again, understanding that it's correct doesn't mean it's easy to get your mind around the why -> because there're at most (N-1) node in the shortest path, I have to do the loop (N-1) times?

After you get the induction, the most important point in my opinion is that The BF process in each loop doesn't guarantee a specific order of edges: you may process the edges in ANY order and still reach the correct answer after N-1 loops..

Now a very simple case to help you understand: enter image description here

Conclusion: (The part in the example attached). Plus in the worst case scenario, when you have a shortest path that is (N-1) in length, and each i-th loop you only relaxed the i-th node after source node in the shortest path, you're gonna need (N-1) loops. In our example, in case 2, for node 3, the 1st loop only managed to relax node 2, which is the 1st node after source on P(1,3), so you need another loop to relax.

Upvotes: 3

snakile
snakile

Reputation: 54521

The reason that only d[y] and d[t] are updated in the first iteration is that these two vertices are the only ones whose estimation of the distance from s can be improved. To be more precise, in order for d[v] to be updated at a particular iteration, there must be an edge (u,v) such that d[u]+w(u,v)<d[v]. That is, we must be able to improve our estimation of the distance from s to v in order to update d[v]. In the first iteration, the value of d[u]=inf for every vertex u (except s). Therefore, if v is not a neighbor of s, then u is not s, and hence the value of d[u]+w(u,v) equals inf+w(u,v)=inf. This means we cannot improve our estimation of d[v]. This is why only the neighbors of s are updated in the first iteration even though the algorithm iterates over all the edges of the graph.

As for why we need n-1 iterations, the following two guarantees are achieved after i iterations:

  1. if d[u] is not inf, then there exists a path of length d[u] from s to u.
  2. if there is a path from s to u with at most i edges, then d[u] is at most the length of the shortest path from s to u with at most i edges.

The number of edges of the shortest path from s to u cannot exceed n-1 (assuming no negative cycles). Therefore, the two guarantees (which can be proved by induction on i) imply that after n-1 iterations, if there's a simple path of a particular length from s to u, the algorithm finds it.

Upvotes: 6

Related Questions