Register

GATE CSE 2004 | Question: 44

• edited by
15,766 views
37 votes
37 votes

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source.

In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

  1. $P,Q,R,S,T,U$
  2. $P,Q,R,U,S,T$
  3. $P,Q,R,U,T,S$
  4. $P,Q,T,R,U,S$
• edited by
User Avatar

3 Answers

Best answer
33 votes
33 votes

Answer is (B). In Dijkstra's algorithm at each point we choose the vertex with the shortest distance from the set of vertices in the shortest path found so far and add the edge connecting it to the shortest path.

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

63 votes
63 votes
11 answers
4
Kathleen asked Sep 12, 2014
27,945 views
GATE CSE 2008 | Question: 45
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance toonly vertex $a$only vertices $...
User Avatar
Link Copied!