CODEWITHSUNDEEP
algorithmgraphdijkstra
SBylemans
SBylemans

Reputation: 1764

Dijkstra's end condition

With Dijkstra you use the end-condition

   while(!q.isEmpty()){
       //Some code
   }

But if you know the end node, is it not possible to change the end-condition to

   while(!q.peek().equals(endNode){
       //Some code
   }

Every implementation of Dijkstra I have seen uses the earlier, but the later is faster when you know the end node. Or is this not Dijkstra anymore?

Upvotes: 6

Views: 7072

Answers (1)

Fred Foo
Fred Foo

Reputation: 363787

Depends on what you want the algorithm to do. The original Dijkstra's algorithm computes the length of the shortest path from the source to each other vertex. If you have a single target vertex, you can cut the algorithm short after you've popped the target off the queue.

Correctness of the shortcut can be easily proven: Dijkstra's never changes the shortest-path length of a node that it has already popped off the queue, so you know you're looking at the length it would return if you continued running the algorithm until the queue was empty.

Upvotes: 15

Related Questions