Why can't we replace Dijkstra's priority queue with a regular queue? 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?
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.