2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What is your question? $\endgroup$
    – D.W.
    Dec 6, 2020 at 1:20
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Dec 6, 2020 at 7:23
  • $\begingroup$ 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). $\endgroup$
    – greybeard
    Dec 7, 2020 at 10:27

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ in your original question there is no reference to a modified algorithm. The answer refers to the Bellman Ford original algorithm. By the way, the example given in your comment can not be understood, since you are not providing the full input graph and the weights on each of the edges. $\endgroup$ Jan 6, 2021 at 15:09
  • $\begingroup$ The link you provide has two questions. The first one is exactly the one which I have answered, providing full details: besides the standard induction proof there is nothing that can be really usefully added. The second claim, the one related to the weights on a shortest paths is obviously false, as already shown in the answer to the question you linked to. Regarding the variants available in Jeff Erickson's book, the first is just a minor variation due to Moore (which is faster) and the other three are just the steps needed to simplify the original algorithm based on dynamic programming. $\endgroup$ Jan 6, 2021 at 17:14
  • $\begingroup$ 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$). $\endgroup$ Jan 7, 2021 at 9:55
  • $\begingroup$ What you mean exactly by "clean comments" ? $\endgroup$ Jan 16, 2021 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.