in Algorithms edited by
15,369 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$
in Algorithms edited by
15.4k views

1 comment

B
0
0

3 Answers

33 votes
33 votes
Best answer

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

4 Comments

Choosing smallest edge in Dijkstra, ??
0
0
Fine now?
0
0

The path visualized :-

1
1
10 votes
10 votes

Answer will be "B" 

0 votes
0 votes

 

Option B :

Answer:

Related questions