11
$\begingroup$

I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I understand why Dikjstra doesn't work for a graph with negative weights. So in the Bellman-Ford algorithm we decide to update all nodes and their neighbors even though they might be visited before. My confusion can be summarized in a couple of questions:

  1. Why running the BF algorithm once won't make sure that all nodes' distances have the minimum distance from the source?

  2. Why do we have to run BF for N-1 (N: number of nodes) times to make sure all the nodes have the minimum distance from the source? Is it sort of because there are negative weights? How negative weights complicate things?

Improve this question
$\endgroup$
2
  • $\begingroup$ "Why do we have to run BF for N-1 times" -- we don't. You seem to have misunderstood something. $\endgroup$
    – Raphael
    Dec 10, 2015 at 9:20
  • $\begingroup$ Please refer to my answer here, with example, and hopefully it's easier for you fellows to understand: stackoverflow.com/questions/49263065/… $\endgroup$
    – Isaac_Zhu
    Sep 29, 2019 at 9:48

2 Answers 2

Reset to default
9
$\begingroup$

Answering your first question is simple. Try out a few graphs and see for yourself why it doesn't work. As to your second question, $n-1$ is the maximal length of a shortest path in the graph. After $k$ iterations of the Bellman–Ford algorithm, you know the minimum distance between any two vertices, when restricted to paths of length at most $k$. This is why you need $n-1$ iterations. Negative weights have absolutely nothing to do with it.

For a more sophisticated answer, consult the recent paper of Jukna and Schnitger, On the optimality of Bellman–Ford shortest path algorithm. They show that among the class of Bellman–Ford-like algorithms, the Bellman–Ford algorithm is optimal.

Improve this answer
$\endgroup$
0
4
$\begingroup$

The longest possible shortest path from source s to destination $v_k$ can have $|V|-1$ "stops". According to Lemma 24.15 Path-relaxation property in CLRS, after each "relaxation" step, you get $v_i=\delta(s, v_i)$ and this value remains unchanged ever since. So after $|V|-1$ times we must finish finding all results for a single-source shortest path problem. You make easily find a counterexample to say why loop for fewer than$|V|-1$ will fail to find all shortest paths.

Improve this answer
$\endgroup$

Your Answer

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

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