1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.