[Solved]: Why not relax only edges in Q in Dijkstra's algorithm?

Problem Detail: 

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 ?

Asked By : Schwammkopf

Answered By : Marc Khoury

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9120