Project ForgeConsider a directed graph with vertices S, A, B, C, D, E, F, G, T and edges (with weights): S→A=4, S→B=3, S→D=7, A→C=1, C→E=1, B→D=4, D→E=1, D→F=5, D→T=3, E→G=2, E→T=4, G→T=3, F→T=5. 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.
- ASDT
- BSBDT
- CSACDT
- SACET
Explanation
Computing path weights: SDT = 7+3 = 10, SBDT = 3+4+3 = 10, SACET = 4+1+1+4 = 10 (three tied shortest paths of length 10), while SACDT = 4+1+3+3 = 11 is longer. Since the algorithm only updates a vertex's shortest distance on a STRICTLY shorter discovery (not on ties), the specific path retained depends on discovery order as Dijkstra's algorithm processes vertices by increasing tentative distance — tracing this order through the graph shows the path that survives without being strictly improved upon is S→A→C→E→T (SACET).
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.