Why not relax only edges in Q in Dijkstra's algorithm?

Question

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 ?

Answer 1

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.

Answer 2

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.