Same question explained here

https://stackoverflow.com/questions/13249057/dijkstra-find-shortest-path-in-directed-graph

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+27 votes

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.

- $\text{SDT}$
- $\text{SBDT}$
- $\text{SACDT}$
- $\text{SACET}$

0

Same question explained here

https://stackoverflow.com/questions/13249057/dijkstra-find-shortest-path-in-directed-graph

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

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.

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.

+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**

+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

@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.

+2

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.

+5 votes

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

Answer seems to be D. could be checked directly.

+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

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...

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,555 answers

146,265 comments

62,304 users