While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma:
After k (k >= 0) iterations of relaxations, for any node u that has at least one path from s (the start node) to u with at most k edges, the distance of from s to u is the smallest length of a path from s to u that contains at most k edges.
We prove this lemma using mathematical induction as follows:
- Base case: After 0 iteration, all distance values are infinity, but for s the distance is 0, which is correct!
- We assume the lemma is true for k iterations and now we have to prove it for k+1 iterations!
- Before k + 1th iteration, dist[u] (which is the distance of u, from s) is the smallest length of a path from s to u containing at most k edges. Each path from s to u goes through one of the incoming edges (v, u). Relaxing by (v, u) is comparing it with the smallest length of a path from s to u through v containing at most k + 1 edges -- this proves it!
Now, I have doubt in the 3rd point. Let us say that in the k+1-th iteration the node u has got a new distance after some edge relaxations, now according to the above lemma, this distance must be the shortest of the distances of all the paths with at most k+1 edges from s to u. Now, consider another node w, that has an edge to it, from u. Now, the length of the path form s to w via v will have at most k+2 edges, but if this edge is relaxed to reduce the dist[w], then in k+1-th iteration itself, we will have included a path (to w) that has almost k+2 edges right? Is it not a contradiction? Can it not happen?
To be more precise I am unable to reason the fact that, the lemma holds true throughout the k+1-th iteration -- I am not convinced with the 3rd step of the proof.
If someone can explain to me the 3rd step or whole proof more clearly, it would be really helpful! If someone can share a proof that does not use mathematical induction will also be really helpful!