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


  min.priority + weight(min,v) &lt; 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) &lt; v.priority must be false, otherwise we would have found a shorter path to v which is a contradiction.