Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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  
share|improve this question
    
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. –  moller1111 Dec 28 '12 at 16:05
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
2 further questions: - do you mean with the topological order, the alphabetical sorting i mentioned above? - why don't we sort it first and than apply the rest of the algo? Wouldn't that be quicker ? –  moller1111 Dec 28 '12 at 16:07
    
and the 3.question: given that ordering without the outer loop, would the algorithm be not as fast as the Djisktra's ? –  moller1111 Dec 28 '12 at 16:16
    
The topological order consists of the vertices ordered according to their distance from the source. While finding this order is prima facie easier than finding the distances themselves, the way one usually does that is by finding the distances first, so it can't make the algorithm any faster. –  Yuval Filmus Dec 28 '12 at 16:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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