# Bellman Ford facts and specific 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?

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.

• What is your question? – D.W. Dec 6 '20 at 1:20
• The limit for path length doesn't seem to hold when we check all edges simultaneously exactly. The model used if not mentioned otherwise is RAM. – greybeard Dec 6 '20 at 7:23
• The hyperlinked Stanford course material seems to be a different edition from the one embedded in your question - more readable for not superimposing script and formulae. As far as Can you please add…? is to be interpreted literally as a question (instead of the prompt I seem to have failed to communicate politely), it remains unanswered: I don't know whether you can name source or originator (judging from the material linked, the latter may be difficult) - you did not update your question (as of now). – greybeard Dec 7 '20 at 10:27

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).
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.
• Your counter-example is wrong: in $k$ iterations the algorithm is only considering paths of length $k$. Try running BF and you will se that after 2 iterations only the paths $s$-->$t$ and $s$-->$u$ have been correctly computed (the distance for $s$-->$v$ will still be $\infty$). – Massimo Cafaro Jan 7 at 9:55