Bellman Ford facts and specific question

Question

The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following: $d(v)>d(u)+w(u,v)$ holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)$ is the length of best path was found for vertex $u$.

If in any step there is no update for all vertexes, the algorithms terminate.

If Bellman-Ford will be used for finding all shortest paths from vertex $s$ in graph $G$ with $n$ vertex, terminate after $k < n$ iteration then following is True:

number of edges in all shortest paths from $s$ is at most $k-1$

I think some times this is true and sometimes is false (when we check all edges simultaneously... maybe this is wrong), but I need a clear definition for the above sentence or a small example about logic. I need verification of the above fact. is it always true? why?

New Updates:

The above statement is dependent on the implementation of your algorithm (at least I think).

Which implementation makes it true and under which condition it becomes false...

I see 4 version of Belman Ford on This Jeff Erricson Algorithm Book on Page 295.

Answer 1

The claim is true. Any correct implementation of Bellman-Ford must guarantee this. Think about an arbitrary shortest path from $s$ to $v$. Besides being a shortest path with regard to the total weight, it must also satisfy another property: the path must be also shortest with regard to the number of edges used. In other words, the algorithm wants to determine shortest paths that are also simple paths (no vertices are repeated, i.e., all of the vertices in the path are distinct).

Why there is a need to ask for shortest and simple paths? Because there are obviously shortest paths with regard to the total weight that are not simple, e.g. there can be zero weight cycles. Bellman-Ford assumes that there are no negative weight cycles (the algorithm is able to detect a negative weight cycle) but there can be zero weight cycles, since they are actually allowed by the definitions. The problem caused by a zero weight cycle is that you can use it to arbitrarily augment the number of edges of a shortest path, by putting it somewhere in the middle of a shortest path. The total weight will remain the same, so the path will be a shortest path with regard to the weight, but not with regard to the number od edges composing it. This is the reason why you want shortest paths which are simple as well. The algorithm rules out zero weight cycles, throwing them away.

Now, everything follows immediately. A simple path can not have more than $|V| - 1$ edges: that is exactly the number of passes done by Bellman-Ford (since we assume no negative weight cycles, a shortest path can visit each vertex at most only once). Given a path $v_0 = s$ -> $v_1$->...->$v_k=v$ during the $i$th iteration the algorithm relaxes all of the edges; in particular, during iteration $i$ it relaxes the edge $(v_{i-1}, v_i)$. Therefore, after $i$ iterations the algorithm has correctly set the distance of vertex $v_i$ from $s$. And we know that the input graph does not contain negative weight cycles, that the path is simple and that a longest simple path may have at most $|V|$ -1 edges. So, the algorithm is correct.