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

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered.

  1.  $\text{SDT}$
  2.  $\text{SBDT}$
  3.  $\text{SACDT}$
  4.  $\text{SACET}$
asked in Algorithms by Boss (18.3k points)
edited by | 3.8k views
0
+3
0
Seriously i found all  comments but i cant find why b is skipped and why not SBDT as a ans? Could anyone please explain in simple way without complication
0
@kadhar Make Minimum Spanning Tree (check the geeksforgeeks link above) then you will understand.
0
Dijkstra's sequence will be S, B, A, C, E, D, G, T, F but our problem is to find the shortest path from S to T.

Using the above table you can find easily.

first, go to the column of T and see the last entry cost = 10 and parent is E.  It means E -> T.

Now again go to the column of E and see the last entry cost = 6 and parent is C. It means  C -> E

and Hence C -> E -> T

Now again go to the column of C and see the last entry cost = 5 and parent is A. It means A -> C

and Hence A -> C -> E -> T

Now again go to the column of A and see the last entry cost = 4 and parent is S. It means  S -> A.

and Hence Path is S -> A -> C -> E -> T

total cost is 4 +  1 + 1 + 4 = 10.

4 Answers

+30 votes
Best answer

Relaxation at every vertex is as follows

Note the next vertex is taken out here:

  A B C D E F G T
S $4$ $3$(by s) $\infty$ $7$ $\infty$  $\infty$  $\infty$  $\infty$ 
B $4$(by s)   $\infty$ $7 \because (4+3  \ also \ =7)(S \to d)$ $\infty$  $\infty$  $\infty$  $\infty$ 
A     $5(S \to B \to A)$ $7$ $\infty$ $\infty$ $\infty$ $\infty$
C       $7$ $6(S \to B \to C)$ $\infty$ $\infty$ $\infty$
E       $7(S \to D)$   $\infty$ $8(S \to A \to C \to E)$ $10(S \to A \to C \to E)$
D           $12(S \to B \to D)$ 8 $10$(same so no change)
E           $12$   $10$
T           $12$    

Now We see for $S$ to $T$ its $(S \to A \to C \to E \to T)$

which is Option : D

answered by Active (2.1k points)
edited by
0
For step 1: why B(though S->B path with wt 3) is taken out compared to S->A with wt 4?
+3

it's because Dijkstra’s shortest path Algo Says always relax the min from the source and add that to visited now compare the min from newly added vertex and previous vertex from source and do relaxation bcz of that vertex at every node  .........if same or more no change ...if less Change the value of the vertex 

+1
Hi , I didn't get this point. Why B is skipped and A is selected .Could you please explain in details.
0
Because we have to see S to T therefore we will see the relaxation on T which are done by SAEC.
0
@abhijit Vertex B is nor skipped when you will follow the dijkstra algo. Then DISTANCE OF D already 7 fRom S so wont be updated during relaxation of B so after completing the dijkstra u will  SACET minimum path for s to T.
+1
@khushtak b is skipped in first pass which contradict this algo.
+2
Dijkstra's sequence will be S, B, A, C, E, D, G, T, F but our problem is to find the shortest path from S to T.

Using the above table you can find easily.

first, go to the column of T and see the last entry cost = 10 and parent is E.  It means E -> T.

Now again go to the column of E and see the last entry cost = 6 and parent is C. It means  C -> E

and Hence C -> E -> T

Now again go to the column of C and see the last entry cost = 5 and parent is A. It means A -> C

and Hence A -> C -> E -> T

Now again go to the column of A and see the last entry cost = 4 and parent is S. It means  S -> A.

and Hence Path is S -> A -> C -> E -> T

total cost is 4 +  1 + 1 + 4 = 10.
0
there is typo in second last row of table it should be G and not E.
+1

adding bit more description to above answer , 

even though option a ,b ,d all three 

  1.  SDT
  2.  SBDT
  3.  SACET

gives 10 .

but we first found distance 10 path to T via SACET

hence even if nodes are confirmed in sequence SBACEDGTF 

i.e D confirmed after E , path to T don't go via SDT.

+5 votes

Dijkstra algorithm is such that it selects shortest edge for adjacent nodes.

It selects shortest path having maximum number of shortest edges, for non adjacent.

Answer seems to be D. could be checked directly.

answered by Active (3.2k points)
0
provide some explanation on your point.
+2 votes
Ans is d

But its taking too much time for me to get the ans..what is the best way to solve this question with optimal time.can any1 suggest
answered by Loyal (8.1k points)
+7
If there's only single shortest path from source to destination then no need to apply algo directly find the path with eye sight..but if there are multiple shortest path then we have to apply the algo..but yeah tricks are everytime there..in this question they want to know your "relaxation" concept of dijkstra's algo..just focus on target vertex T now think about all the vertex which are directly connected with it(E,G,D) now out of these three which one would be relax first that would be the second last vertex from S to T.and that thing we can directly guess with eye sight as to E its 6 and for D its 7 ..now EGT=5 ET=4 so select ET...
+1
not getting.
0 votes

Answer D is correct.

D)S->A->C->E->T

answered by (141 points)


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

40,903 questions
47,555 answers
146,265 comments
62,304 users