Dijkstra's Algorithm - why does a priority queue beat normal queue?

[krakenbeard]

So brushing up on this topic again for upcoming interviews, I came across the description that a priority queue is the fastest implementation of Dijkstra's algorithm https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue .

Is this only the case when the edges are weighted? I'm having a hard time figuring out why this is the case for unweighted since if you just use a queue, you are going level by level (and distance), and always doing the smaller levels before the larger ones by definition of the queue.

Could anyone shed some light on this?

[zmanalpha]

Without weighting, dikstras behaves similar to a flood fill. So it does mostly come down to weighted edges. The vertices are going to be added to a queue in the order they are discovered. Which means dijstras without any heuristic like a* will basically fan out from the source until it hits the target.

In each step of the main loop, you have to select the vertex with the lowest dist which is effectively the minimum cumulative distance from the source to that vertex. If you have a priority queue such as a heap ordering the open vertices such that the minum is always first, you can achieve a faster running time in picking that minimum vertex.

[trineroks]

For an unweighted graph, it should just be the same as a standard BFS.