algorithmpriority-queueshortest-pathdijkstra

Priority queue implementation with the Dijkstra


The question asks about the maximum number of elements that can be present in the priority queue at any given time during the execution of Dijkstra's algorithm on the given graph.

I coudn't understand how the 8 is the maximum number of vertices present

Graph on which we have to implement Dijkstra: Graph on which we have to implement Dijkstra


Solution

  • I worked this by hand for your graph, and recommend you do the same.

    The quick summary is that after processing nodes 0, 1, 7, 6, and 5 (with distances 0, 4, 8, 9, and 11, respectively) the priority queue now contains the following eight pending evaluations, which are evaluated shortest-distance-first:

    distance    scheduling edge
       12           1 -> 2
       15           1 -> 7
       15           7 -> 8
       15           6 -> 8
       15           5 -> 2
       19           7 -> 1
       21           5 -> 4
       25           5 -> 3
    

    Note that several of these have the same destination vertex, but they remain in the priority queue until that destination has been reached and labelled.

    After removing the transaction with distance 12, all remaining vertex arrivals have no more than one edge going to a vertex that isn't already labelled as completed, so the priority queue remains the same size or decreases as each transaction is removed for evaluation.