Reputation: 6093
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.
My Answer is SBDT but in solutions it is giving SACET I am not able figure out why..
Upvotes: 1
Views: 18687
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
Reputation: 55639
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