edited by
15,353 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

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
Answer:

Related questions

66 votes
66 votes
9 answers
2
Kathleen asked Sep 18, 2014
23,687 views
The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined bythe instruction set architecturepage sizenum...