Clarification in the proof for the Bellamn-Ford algorithm

Question

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:

1. Base case: After 0 iteration, all distance values are infinity, but for s the distance is 0, which is correct!
2. We assume the lemma is true for k iterations and now we have to prove it for k+1 iterations!
3. 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!

Answer 1

The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion.

The correct claim is the following: Consider the values of $\text{dist}[\cdot]$ computed at the end of the $k$-th iteration of Bellman-Ford. For any vertex $u$, let $d^{(k)}_u$ be the length of the shortest path from $s$ to $u$ that uses at most $k$ edges (if no such path exists then $d^{(k)}_u = +\infty$). It holds that $\text{dist}[u]\le d^{(k)}_u$.

Notice the $\le$ sign!

The above claim implies that, after the $(n-1)$-th iteration all distances stored in $\text{dist}[\cdot]$ are smaller than or equal to the true distances in the graph.

Clearly, it also holds that all the distances stored in $\text{dist}[\cdot]$ are larger than or equal to the true distances in the graph (since every time you a distance is updated, the new distance is always the length of some path from $s$).

Combining the previous two properties, you can conclude that $\text{dist}[\cdot]$ stores the exact distances from $s$, i.e., that the Bellman-Ford algorithm is correct.

---

Let me prove my claim formally. To avoid confusion this is the pseudocode of the Bellman-Ford algorithm I will be using:

Bellman-Ford(G=(V,E; w), s):
  For u in V:
    dist[u]=+infinity

  dist[s]=0
  For k=1,..., n-1:
    For (v,u) in E:
      dist[u] = min(dist[u], dist[v] + w(v,u))

The proof is by induction on $k=0, \dots, n-1$ (where the end of the $0$-th iteration corresponds to the state of the algorithm just before the first iteration of the outer for loop).

The base case is $k=0$. There is only one vertex $u$ such that the path from $s$ to $u$ uses $k=0$ edges, namely $u=s$. The claim holds for $s$ since $\text{dist}[s] = 0 = d_s^{u}$. For $u \neq s$, the claim holds since $\text{dist}[u] = +\infty = d_u^{(k)}$.

Suppose now that the claim holds for $k-1 \ge 0$. We will prove that it also holds for $k$. Consider any vertex $u \in V$, let $P$ be the shortest path from $s$ to $u$ that uses at most $k$ edges, let $w(P)$ be the (weighted) length of $P$, and let $|P|$ denote the number of edges of $P$. We distinguish two cases:

If $|P| < k$ then $d_u^{(k)} = d_u^{(k-1)}$ and, by inductive hypothesis, at the end of the $(k-1)$-th iteration of the outer for loop we had $\text{dist}[u] \le d_u^{(k-1)} = d_u^{(k)}$. The claim follows since the values of $\text{dist}[\cdot]$ never increase during the execution of the algorithm.

If $|P|=k$ then $|P| \ge 1$. Let $(v,u)$ be the last edge of $P$ and let $P'$ be the subpath of $P$ from $s$ to $v$. Let $\delta$ be the value of $\text{dist}[v]$ at the end of the $(k-1)$-th iteration of the outer for loop. By the suboptimality of shortest paths we know that the (weighted) length $w(P')$ of $P'$ is exactly $d_v^{(k-1)}$. Moreover, the inductive hypothesis ensures that $\delta \le d_v^{(k-1)}$. Consider the situation at end of the iteration of the inner for loop that considers edge $(v,u)$, during the $k$-th iteration of the outer for loop. Since values of $\text{dist}[\cdot]$ never increase, we must have: $$ \begin{align*} \text{dist}[u] &\le \text{dist}[v] + w(v,u) \\ &\le \delta + w(v,u) \\ &\le d_v^{(k-1)} + w(w,v) \\ &= w(P') + w(v,u) = w(P) = d_u^{k}. \end{align*} $$ Once again, since the values of $\text{dist}[\cdot]$ never increase, the above inequality must also hold true at the end of the $k$-th iteration of the outer for loop.