The Dijkstra Trace and the Improved Path

Ada re-derives this chapter’s own numbers step by step, at full precision

ADA · CALCULATION AUDIT

The Dijkstra Trace and the Improved Path

A five-router topology links R1 directly to R3 with weight 5, but also links R1 to R2 with weight 1, R2 to R4 with weight 2, and R3 to R4 with weight 1. The lab’s acceptance standard demands the trace show at least one tentative path that improves after a later step. This audit asks the question that requirement invites: does R3’s path really improve from 5 down to 4 once R4 is settled, and does that make R2 the next hop for R3, R4, and R5 alike?

Companion to the chapter Lab: Routing Algorithms by Hand — every number here comes from that chapter.

Ada: The acceptance standard for Lab 2 asks for one tentative path that improves after a later step. That improvement is the whole reason Dijkstra beats a diagram glance, so let me re-run the five-router trace from R1 by hand and check every settle. The edges are R1-R2 = 1, R1-R3 = 5, R2-R4 = 2, R3-R4 = 1, R4-R5 = 3.

• Settle R1 = 0. Frontier becomes R2 = 1 and R3 = 5.
• Lowest frontier is R2 = 1; settle it. Relax R4 through R2: 1 + 2 = 3.
• Frontier is now R3 = 5, R4 = 3. Lowest is R4 = 3, settled before R3 because 3 < 5.
• Relax R3 through R4: 3 + 1 = 4. That beats the direct edge R1-R3 = 5, so R3 improves 5 -> 4 – the required improved tentative path.
• Relax R5 through R4: 3 + 3 = 6. Settle R3 = 4, then R5 = 6.

Final shortest-path costs from R1: R2 = 1, R4 = 3, R3 = 4, R5 = 6. Each of R3, R4, and R5 has a shortest path whose first hop is R2, so R2 is the next hop for all three.

The audit confirms why metric-before-lookup would go wrong here: R3’s attractive direct edge (5) is not its shortest path (4 via R4), and only a full frontier trace – not the diagram – surfaces that the cheaper route arrives one hop later.

Every number above is taken from the chapter’s own material and re-derived step by step.