Suppose we run Dijkstra’s single source shortest-path algorithm on the…
2004
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?
- A.
P, Q, R, S, T, U
- B.
P, Q, R, U, S, T
- C.
P, Q, R, U, T, S
- D.
P, Q, T, R, U, S
Attempted by 169 students.
Show answer & explanation
Correct answer: B
Final order of vertices: P, Q, R, U, S, T
Initialize distances from P: P = 0; Q = 1 (via P); S = 6 (via P); T = 7 (via P); R = ∞; U = ∞.
Choose Q (smallest tentative, distance 1). Relax edges from Q: update R = 2 (via Q) and improve S = 5 (via Q).
Choose R (distance 2). Relax R → U: update U = 3 (via R).
Choose U (distance 3). No outgoing relaxation gives a shorter path to any remaining vertex.
Choose S (distance 5). Relaxations from S would give T = 8 (via S) and U = 7 (via S), neither improves the current values.
Choose T (distance 7). All shortest-path distances are now finalized.
Why other orders fail:
Selecting S before U after processing R is wrong because U has distance 3 (via R) while S has distance 5; Dijkstra must pick the smaller tentative distance first.
Choosing T before R is wrong because R's tentative distance (2) is much smaller than T's tentative distance (7).
A video solution is available for this question — log in and enroll to watch it.