CODEWITHSUNDEEP
algorithmdata-structuresdijkstra
Nishant Kumar
Nishant Kumar

Reputation: 6093

Dijkstra: Find Shortest path in directed graph

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 Dijstra?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. enter image description here

My Answer is SBDT but in solutions it is giving SACET I am not able figure out why..

Upvotes: 1

Views: 18690

Answers (2)

Jerry
Jerry

Reputation: 109

Run it in http://dracos.co.uk/maths/dijkstra/ Answer is SDT. Reason: After node S, its immediate neighbors are considered ie:A(4),D(7),B(3) Now immediate neighbors of these nodes are considered. We arrive at SDT(10) before node C is considered because C is not the immediate neighbor of S. Answer: SDT

Upvotes: -2

Bernhard Barker
Bernhard Barker

Reputation: 55649

Dijkstra's Algorithm picks nodes as follows:

B(3) from S
A(4) from S
C(5) from A
E(6) from C
D(7) from S or B
G(8) from E
T(10) from D or E

Thus the shortest path to T is SBDT, SDT or SACET.

But because of "the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered", when E is visited, T's prior node for the shortest path will be set as E and not changed again.

Thus the answer is SACET.

Upvotes: 4

Related Questions