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?
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.