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.

Can someone tell me why almost in every book/website/paper authors use the following:

foreach vertex v in Adjacent(u)
    relax(u,v)

when relaxing the edges, instead of:

foreach vertex v in Adjacent(u)
    if (v is in Q)
        relax(u,v)

This is extremely confusing for someone when learning the algorithm. Is there any reason why the people are omitting the IF ?

Anyway I wrote a semi-Javascript (I changed it here to a readable syntax) implementation of Dijkstra and I wanted to be sure if it is correct because of this IF case. Here is my code excluding the initialising:

while (queue.length != 0)
    min = queue.getMinAndRemoveItFromQ()
    foreach v in min.adjacentVertices
        // inspect edge from "min" to "v"
        if ( queue.contains(v) AND min.priority + weight(min,v) < v.priority )
            v.priority = min.priority + weight(min,v)
            v.pre = min

Is this implementation correct or am I missing something ?

share|improve this question
    
You don't state what $Q$ is. It might contain all unsettled vertices, or it might only contain discovered unsettled vertices. In the former case, the condition is right, in the later it's wrong. –  Jan Hudec Jan 25 '13 at 13:03

2 Answers 2

up vote 6 down vote accepted

The condition

min.priority + weight(min,v) < v.priority

can only be true if $v$ is in the queue. If a vertex $v$ has been removed from $Q$ the invariant of Dijkstra's algorithm guarantees we've already found the shortest path to $v$.

Edit: Proof Sketch Suppose v isn't in Q. Then we must have already found the shortest path to v. Now if we later examine a vertex u connected to v, the condition min.priority + weight(min,v) < v.priority must be false, otherwise we would have found a shorter path to v which is a contradiction.

share|improve this answer
    
well according to this we must add to the code: if (v is in Q) too, which is not added in the books/papers etc. And i wonder why. –  Hasan Tahsin Jan 23 '13 at 23:49
    
The test if(v is in Q) is redundant, since the second condition can only be true if v is in the Q. –  Marc Khoury Jan 23 '13 at 23:52
    
is it also redundant if we have an undirected graph? –  Hasan Tahsin Jan 23 '13 at 23:55
    
Yes, it is still redundant. –  Marc Khoury Jan 23 '13 at 23:59
1  
Suppose $v$ isn't in $Q$. Then we must have already found the shortest path to $v$. Now if we later examine a vertex $u$ connected to $v$, the condition min.priority + weight(min,v) < v.priority must be false, otherwise we would have found a shorter path to $v$ which is a contradiction. –  Marc Khoury Jan 24 '13 at 0:38

It depends on how they define what is in the queue ($Q$). There are two options:

  1. Initially all vertices are added in the queue, the source with distance $0$, all the other with distance $\infty$.
  2. Initially only source is added with distance $0$, other vertices are added when discovered.

Now in the first case, the condition might be added, but is redundant. If $v \not\in Q$, than we already know $d(v)$ and we know that $d(v) \le d(u)$ ($u$ being current vertex), so $d(u) + d(u,v) \ge d(v)$ given the precondition of Dijkstra's algorithm that $d(u,v) \ge 0$.

But in the second case, the condition is wrong, because $Q$ only contains discovered vertices, but we need to process undiscovered vertices as well.

Given that a heap structure does not allow efficient membership check nobody wants to confuse newbies into performing this check when comparing the tentative distances is only slightly slower than checking "settled" flag and need to keep a "settled" flag around might easily offset it's possible benefits anyway. I know at least one practical implementation that keeps and uses such flag. It does so mainly to reuse code from breadth-first search and is accompanied by an alternate implementation that does not.

Also note that many applications of Dijkstra's algorithm stop it when specific vertex is settled, specific diameter reached, two parallel runs meet or some other stopping condition is met long before the whole graph is even discovered, in which case the second definition is more efficient (you don't add the vertices that won't be needed) and I don't see any case where the first would actually be more efficient. And as established above, in the second case, the condition can't be added.

share|improve this answer
    
+1 for the two ways the queue can be used. –  Paresh Jan 25 '13 at 13:28

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.