[Solved]: Bellman-Ford: shortest path

Problem Detail: 

my assumption:
- we have an undirected graph with only positive edges
- the edges are sorted alphabetically:
    e.g A-B, A-C, B-D
    and e.g not C-A, D-B, A-B

I do not understand, why we need the first loop (line 1) here. I executed the algorithm on paper on 3-4 different undirected graphs. And everytime the first iteration of line1 ends, the algorithms finishes to find the shortest path and the remaining iterations are doing just garbage check.

Can anyone give a concrete graph example where we need the first loop? Does the first loop to do something with the negative edges or edge direction perhaps ?

1 for i=1 to vertices.length-1 2    foreach e in edges 3        if e.v2.cost > e.v1.cost + e.weight 4            e.v2.cost := e.v1.cost + e.weight 5            e.v2.pre := e.v1   

Asked By : Schwammkopf

Answered By : Yuval Filmus

You're correct that there is always an ordering of the vertices for which this algorithm will converge in one iteration, namely the topological ordering given by the shortest-path spanning tree. However, in general the vertices won't be given to us in that order.

Consider for example a path $(C,A),(A,B)$, where $C$ is the source. The algorithm will go through the edges in the order $(A,B),(C,A)$, and will need two iterations to converge.

Here is another example, in which the source it the first vertex: a path $(A,C),(C,B),(B,D)$, where $A$ is the source. The algorithm will go through the edges in the order $(A,C),(B,D),(C,B)$, and will need two iterations to converge.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7628