Bellman-Ford algorithm proof of correctness

Question

I'm trying to learn about Bellman-Ford algorithm but I'm stucked with the proof of the correctness. I have used Wikipedia, but I simply can't understand the proof. I did not find anything on Youtube that's helpfull. Hope anyone of you can explain it briefly. This page "Bellman-ford correctness can we do better" does not answer my question.

Thank you.

Answer 1

Let's see the problem from the perspective of dynamic programming of a graph with no negative cycle.

We can visualize the memoization table of the dynamic programming as follows:

The columns represent nodes and the rows represent update steps(node 0 is the source node), and the arrows directing from one box in a step to another in the next step are the min updates(step 0 is the initialization).

We choose one path from all shortest paths and illustrate why it is correct. Let's choose the 0 -> 3 -> 2 -> 4 -> 5. It is the shortest path from 0 to 5, we can choose any other one otherwise. We can prove the correctness by reduction. The initial is the source 0, and obviously, the distance between 0 and itself should be 0, the shortest. And we assume 0 -> 3 -> 2 is the shortest path between 0 and 2, and we are going to prove that 0 -> 3 -> 2 -> 4 is the shortest path between 0 and 4 after the third iteration.

First, we prove that after the third iteration the node 4 must be fixed/tightened. If node 4 is not fixed it means that there is at least one path other than 0 -> 3 -> 2 -> 4 that can reach 4 and that path should be shorter than 0 -> 3 -> 2 -> 4, which contradicts our assumption that 0 -> 3 -> 2 -> 4 -> 5 is the shortest path between 0 and 5. Then after the third iteration, 2 and 4 should be connected.

Second, we prove that that relaxation should be the shortest. It cannot be greater and smaller because it is the only shortest path.

---

Let's see a graph with a negative cycle.

And here is its memoization table:

Let's prove that at |V|'s iteration, here |V| is the number of vertices 6, the update should not be stopped.

We assume that the update stopped(and there is a negative cycle). Let's see the cycle 3 -> 2 -> 4 -> 5 -> 3.

dist(2) <= dist(3) + w(3, 2)
dist(4) <= dist(2) + w(2, 4)
dist(5) <= dist(4) + w(4, 5)
dist(3) <= dist(5) + w(5, 3)

And we can obtain the following inequlity from the above four inequalities by summing up the left-hand side and the right-hand side:

dist(2) + dist(4) + dist(5) + dist(3) <= dist(3) + dist(2) + dist(4) + dist(5) + w(3, 2) + w(2, 4) + w(4, 5) + w(5, 3)

We subtract the distances from both sides and obtain that:
w(3, 2) + w(2, 4) + w(4, 5) + w(5, 3) >= 0, which contradicts our claim that 3 -> 2 -> 4 -> 5 -> 3 is a negative cycle.

So we are certain that at |V|'s step and after that step the update would never stop.

My code is here on Gist.

Reference:

1. dynamic programming - bellman-ford algorithm
2. Lecture 14: Bellman-Ford Algorithm