# Bellman-Ford: shortest path

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

• Also, the outermost loop does not have to be run $|V|$ times, but $|V|-1$ times. Running it $|V|$ times does not change the asymptotic complexity though. – Paresh Dec 28 '12 at 16:02
• ok, i edited that too. – A.B. Dec 28 '12 at 16:05

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.