patternMinor
Why not relax only edges in Q in Dijkstra's algorithm?
Viewed 0 times
whyedgesdijkstraalgorithmnotonlyrelax
Problem
Can someone tell me why almost in every book/website/paper authors use the following:
when relaxing the edges, instead of:
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:
Is this implementation correct or am I missing something ?
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 = minIs 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.
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.