Problem Detail: 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:
- Why running the BF algorithm once won’t make sure that all nodes’ distances have the minimum distance from the source?
- 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?
Asked By : Amir Hossein F
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50557 Ask a Question Download Related Notes/Documents
