2
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Paresh
    Dec 28, 2012 at 16:02
  • $\begingroup$ ok, i edited that too. $\endgroup$
    – A.B.
    Dec 28, 2012 at 16:05

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – A.B.
    Dec 28, 2012 at 16:07
  • $\begingroup$ and the 3.question: given that ordering without the outer loop, would the algorithm be not as fast as the Djisktra's ? $\endgroup$
    – A.B.
    Dec 28, 2012 at 16:16
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 28, 2012 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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