Exercise 1: Dijkstra's Algorithm on P-Q-R-S — Possible Solution
====================================================================

GIVEN
------------------------------
Edges: P->Q(2), P->R(9), Q->R(3), R->S(1)
Source: P

STEP-BY-STEP TRACE
------------------------------
Start: dist = {P:0, Q:inf, R:inf, S:inf}. Queue: [(0,P)]

Pop (0,P) -> finalize P=0.
  Relax P->Q: 0+2=2 < inf -> update dist[Q]=2, push (2,Q)
  Relax P->R: 0+9=9 < inf -> update dist[R]=9, push (9,R)
Queue: [(2,Q), (9,R)]

Pop (2,Q) -> finalize Q=2.
  Relax Q->R: 2+3=5 < 9 (R's current distance) -> update
  dist[R]=5, push (5,R)
Queue: [(5,R), (9,R)]   (the (9,R) entry is now stale)

Pop (5,R) -> finalize R=5.
  Relax R->S: 5+1=6 < inf -> update dist[S]=6, push (6,S)
Queue: [(6,S), (9,R)]

Pop (6,S) -> finalize S=6.
  No outgoing edges from S.
Queue: [(9,R)]

Pop (9,R) -> R is already visited (finalized at 5) -> skip this
stale entry.
Queue empty - done.

RESULT
------------------------------
Final distances from P: {P:0, Q:2, R:5, S:6}

R's distance was updated once, from an initial 9 (direct edge
P->R) down to 5, once Q was finalized and revealed the cheaper
route P->Q->R (2+3=5 < 9). This is the same pattern this chapter's
own worked example showed for vertex B - a vertex's first-found
distance is not necessarily final until it is actually popped and
finalized.

WHY THIS WORKS AS AN ANSWER
------------------------------
Every pop-and-relax step is shown in order, including the stale
(9,R) queue entry correctly recognized and skipped rather than
mistakenly re-finalizing R a second time, matching this chapter's
own description of how Dijkstra's priority queue can carry
outdated entries that are simply ignored once encountered.