I am confused why we can't simply use a normal queue instead of a priority queue for Dijkstra's. I agree that you can find the shortest path in fewer iterations of the while loop using a priority queue. However, the runtime will still be O((E + V) log V). However, with a queue, that runtime will be O(E + V). Can anybody find a simple example of where Dijkstra's would fail if we used a queue instead of a Priority Queue?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The whole point of Dijkstra is that you visit the nodes in order of their distance from the source. If you use a queue that isn't a priority queue, then you visit the nodes in whatever "random" order the implementation happens to enqueue them.
answered Jul 26, 2019 at 12:27
$\begingroup$
$\endgroup$
Actually never mind I just realized when you are trying to find A -> F:
A -> C 3
C - > D 3
D -> E 1
E -> F 1
A -> E 10
We will first assign an incorrect value to F (11) based on a longer distance value to E (10). When E is corrected, we would rely on backtracking to edit F's distance which would be more inefficient than using the Priority queue.