3.6k 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}$
edited | 3.6k views
+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.

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

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.
+1
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.
0

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.

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.

0
provide some explanation on your point.
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
+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.

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