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

+31 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}$

+1

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.

0

only when a strictly shorter path to v is discovered.

makes for D. Otherwise SDT is also correct. Isn't it?

0

@KadharHussan if you don't want complicated then apply prims algorithm....and only consider S to T path .

0

@KadharHussan remember the extra condition " **in any iteration, the shortest path to a vertex vv is updated only when a strictly shorter path to vv is discovered**."

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

+5

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.

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

+10

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.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,913 questions

52,293 answers

182,250 comments

67,737 users