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