why PriorityQueue used in Dijkstra's Algorithm?

Question

I've been trying to understand the internals of the Dijkstra's Algorithm to find the shortest path for the weighted graph.

After visiting one vertex, why we have to store the adjacent vertex's into a PriorityQueue instead of normal Queue ?

The reason I'm asking the above question was : I understand with PriorityQueue we can get either biggest / smallest numbers from the Queue. But in the case of Dijkstra's Algorithm, we are anyway visiting all the vertex's irrespective of distance / priority. In such cases why do we need to use PriorityQueue with O(log N) complexity, where normal Queue would do O(1) ?

Am I missing anything ?

Answer 1

The point of Dijkstra's algorithm (and also BFS) is that, when a node gets out of the priority queue (or FIFO queue in BFS), it should have the shortest distance from the source node and the distance would be locked. These nodes will be marked as visited and won't ever go into the queue again. This is why a FIFO queue works fine in BFS, because the weights of each edge is equal and the shortest distance from source would be the minimum number of 'hops'.

Now let's consider this weighted graph:

       (s)
       / \
     2/   |
     /    |
   (a)    |
    |     |
   3|     |
    |     |
   (b)    |100
    |     |
   2|     |
    |     |
   (c)    |
    \     |
    4\    |
      \  /
      (d)

Let's try a FIFO queue to find shortest path from node s.

       Push s:           Queue: [s],    Distance: s:0
Pop s, Push a, d:        Queue: [a, d], Distance: s:0, a:2, d:100
Pop a, Push b:           Queue: [d, b], Distance: s:0, a:2, d:100, b:5
Pop d, Push c:           Queue: [b, c], Distance: s:0, a:2, d:100, b:5, c:104
Pop b, No new neighbors, Queue: [c],    Distance: s:0, a:2, d:100, b:5, c:104
Pop c, No new neighbors, Queue: [],     Distance: s:0, a:2, d:100, b:5, c:104

Clearly it got wrong for nodes c and d, where the shortest distance would be 7 and 11. Using a priority queue would definitely do it right.

Answer 2

There can be multiple ways to reach a vertex, and using a priority queue ensures that we have found the shortest distance to a vertex by the time we visit it.

Consider the following graph:

 a
 |\
1| \3
 |  \
 c---b
   1  \
       \
       ...

When we visit vertex a, we will put vertex b and vertex c into the priority queue with distances of 3 and 1 respectively. If we don't use a priority queue, we might visit b first which is a problem because the shortest distance to b that we currently know is suboptimal.

If we use a priority queue, we can prove that when we explore a vertex there is no path to this vertex shorter than the distance which we currently know. Assume for the sake of contradiction that we visit a vertex b when there is a shorter path to it. Let (u, v) be an edge on the shorter path to b such that u has been visited and v has not been visited. Since u has been visited, we must have added v to the queue, and since v is on a shorter path to b, it's distance must be shorter than the distance to b which means it must have been visited before b. Therefore, we have a contradiction and we know that no shorter path can exist.