The Dijkstra Trace and the Improved Path
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.
See the relationship before changing it
The figure reads from left to right. The blue card is r4-to-r3 edge weight. The middle card applies this page's rule. The green card is alternative path cost. Walk the arrows once: set the input, apply the rule, then read the result with its unit.
The retained audit below checks several chapter fixtures. This model keeps those stated values fixed and changes only r4-to-r3 edge weight, so the numeric fixture does not switch without explanation.
Derive the baseline in four named moves
- 1
Name the input. The chapter baseline is 1 cost.
- 2
Name the relationship. path cost = R1-to-R4 cost 3 + final edge
- 3
Substitute with units. 3 + 1 = 4.00 cost
- 4
Read the result. Keep the unit beside the value. Use it only inside the technical boundary on this page.
Predict, then change r4-to-r3 edge weight
Try Predict the direction of path cost = R1-to-R4 cost 3 + final edge. Test another r4-to-r3 edge weight, then compare alternative path cost.
Observe Relaxation improves the stored path only while the new edge keeps the full route below five. Reset r4-to-r3 edge weight to 1 and compare alternative path cost.
Explain Relaxation improves the stored path only while the new edge keeps the full route below five.
Check yourself
What should you do before trusting a moved-control result?
What does this small model leave out?
Seed Dijkstra with R1 = 0, R2 = 1, and direct R3 = 5; click Check audit after settling the lowest frontier.
R3's tentative cost changes from 5 to 4 after R4 reaches cost 3, and R2 becomes the first hop for R3, R4, and R5.
Edge relaxation changes R3 from 5 to 4 because the settled prefix plus the next edge is cheaper than the stored tentative distance.
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 becomesR2 = 1andR3 = 5. - Lowest frontier is
R2 = 1; settle it. Relax R4 through R2:1 + 2 = 3. - Frontier is now
R3 = 5,R4 = 3. Lowest isR4 = 3, settled before R3 because3 < 5. - Relax R3 through R4:
3 + 1 = 4. That beats the direct edgeR1-R3 = 5, soR3improves5 -> 4– the required improved tentative path. - Relax R5 through R4:
3 + 3 = 6. SettleR3 = 4, thenR5 = 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.
Technical boundaries: The static non-negative graph ignores topology changes, packet loss, asymmetric links, equal-cost tie-breaking, queue delay, and distributed convergence between routers.