0

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

Improve this question
5
  • Is there some specific variant of Dijkstra's algorithm that you were supposed to consider? (the question doesn't specify, but you could infer this from earlier course material) Commented Aug 15, 2024 at 14:09
  • I think we have to use the priority queue only but I am not able to understand how to implement it and how we are getting 8 maximum number of vertices for 9 vertices graph. Commented Aug 15, 2024 at 14:24
  • @VivekNaithani, there are several variants of Dijkstra's algorithm that use a priority queue. Which one is this question referring to? The answer depends on that... Commented Aug 15, 2024 at 14:40
  • I think you’re mistaken in thinking that the PQ entries are vertices. The PQ stores edges to figure out what will be the quickest edge that goes to a new vertex. There can be a lot more edges than vertices. Commented Aug 15, 2024 at 16:46
  • 1
    Labelling vertices or edges of a weighted graph with numbers should be banned. (Is it a blessing digits of Indian-Arab heritage are so common or a curse no alphabet is?) Commented Aug 16, 2024 at 5:18

1 Answer 1

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

You argue the queue to hold edges, I am accustomed to its holding vertices.
@greybeard The destinations available from a given vertex are determined by evaluating edges. In practice people generally want to know the path associated with the shortest path, and in order to backtrack to determine the actual path which was shortest you need to know where you came from, a.k.a. the originating vertex. Pairing a source vertex and a destination vertex is the definition of an edge.
@greybeard When you label a vertex as having been reached for the first time because it popped off the head of the priority queue, how do you know what backtracking information to store? If there are multiple paths by which a vertex can be reached, you need to know which edge you arrived on to identify the shortest path predecessor. That means the PQ should associate both the destination and predecessor info with the distance/priority. Whether you store it as an edge object or as two separate pieces of info, you are de facto storing an edge.
([?no matter? storing an edge] or [a vertex with path info], you are de facto storing an edge keeping edges, there can be multiple ones to the same vertex (2 & 8 in the snapshot you present) leading to a bigger queue.)
@greybeard Yes, there can be multiple edges leading to the same vertex. That's the whole point, the very reason why a priority queue is needed. You can't greedily label a vertex with a known shortest distance from origin when you see it for the first time. There may be alternate paths that you haven't yet encountered, so you add this candidate to the priority queue and only get to finalize it as the correct path when it pops to the top and the destination has not yet been labeled via a different path.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.