The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.2k views

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$
asked in Algorithms by Veteran (59.9k points)
edited by | 2.2k views

2 Answers

+19 votes
Best answer

Answer is (B). In Dijkstra's algorithm at each point we choose the smallest weight edge which starts from any one of the vertices in the shortest path found so far and add it to the shortest path.

answered by Junior (767 points)
edited by
+1
Ans (C) is also possible in this case.. so, what is the answer ? confused about it.
+1
(c )can not be an answer  according to dijikstras algorithm

reaching node R  , edge to S and U from R is relaxed which gives node S value - 4 and node U value as 3 therefore we wil choose U now and after that  S and at the and T
0
Why we prefer S-T(cost to reach from P is 8) over P-T(Cost is 7)?

Is in Dijkstra from a vertex only one outgoing edge(of minimum weight) is allowed?
+6 votes

Answer will be "B" 

answered by Loyal (8.5k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,925 questions
52,325 answers
182,361 comments
67,788 users