Suppose we run Dijkstra’s single source shortest-path algorithm on the…

Final order of vertices: P, Q, R, U, S, T

1. Initialize distances from P: P = 0; Q = 1 (via P); S = 6 (via P); T = 7 (via P); R = ∞; U = ∞.

2. Choose Q (smallest tentative, distance 1). Relax edges from Q: update R = 2 (via Q) and improve S = 5 (via Q).

3. Choose R (distance 2). Relax R → U: update U = 3 (via R).

4. Choose U (distance 3). No outgoing relaxation gives a shorter path to any remaining vertex.

5. Choose S (distance 5). Relaxations from S would give T = 8 (via S) and U = 7 (via S), neither improves the current values.

6. 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).