HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyedgesdijkstraalgorithmnotonlyrelax

Problem

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 ?

Solution

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.

Context

StackExchange Computer Science Q#9120, answer score: 7

Revisions (0)

No revisions yet.