w-29-dijkstra.yml · YAML
YAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAML
# Dijkstra's shortest-path algorithm
# Single-panel chapter widget. Three synchronized panels per Bostock's
# Level-2 white-box convention: priority queue (left), dist[] table (top),
# graph with edge highlight (center). The lazy-deletion idiom is the
# central teaching artifact: two stale-skip events fire in the canonical
# trace (steps 19 and 26).
id: w-29-dijkstra
title: "Dijkstra's shortest-path algorithm"
type: single-panel
level: 2
modes: [preset, randomize, edit]
caps:
node_count: { min: 3, max: 12 }
density: { min: 0.15, max: 0.5 }
weight: { min: 1, max: 99 }
# Hard cap n=12 keeps graph layout legible. The canonical 6-vertex input
# produces a 27-step trace; n=12 with density 0.5 stays under the
# 1000-step animation ceiling.
commands:
- name: pop
payload: { node: 'integer', distance: 'integer' }
description: "Extract-min from the priority queue. Highlight the popped (d, u) entry; remove it from the PQ panel."
- name: settle
payload: { node: 'integer', distance: 'integer' }
description: "Mark the popped node as settled (Wong bluish-green); its distance is now final."
- name: relaxImprove
payload: { from: 'integer', to: 'integer', oldDistance: 'integer | null', newDistance: 'integer' }
description: "An edge relaxation that improved a tentative distance. Update dist[v]; push (newDistance, v) to the PQ; flash the relaxed edge."
- name: relaxSkip
payload: { from: 'integer', to: 'integer', current: 'integer', candidate: 'integer' }
description: "An edge relaxation that did not improve. Highlight the edge briefly in dim color; no PQ change."
- name: staleSkip
payload: { node: 'integer', poppedDistance: 'integer', currentDistance: 'integer' }
description: "Lazy-deletion event. The popped (d, u) entry is stale because dist[u] is already smaller. Discard without scanning neighbors. THIS IS THE CHAPTER'S CENTRAL TEACHING MOMENT."
- name: done
payload: { distances: 'array', parents: 'array' }
description: "All reachable nodes settled; PQ drained. Color the shortest-path-tree edges; display final dist[]."
static_fallback:
generator: jsdom
output: site/static/widgets/w-29-dijkstra-fallback.svg
keyframes_used: [0, 8, 18, 26]
# Override: the lazy-deletion event at step 19 is forced as a static
# keyframe so reduced-motion readers see exactly which entry fires the
# stale-skip and why.
panels:
default:
chapter: "8.9"
label: "Dijkstra on a 6-vertex weighted DAG"
canonical_input: |
nodes: [A, B, C, D, E, F]
edges (directed, weighted):
A->B 7 A->C 9 A->F 14
B->C 10 B->D 15
C->D 11 C->F 2
D->E 6
F->E 9
source: A
expected dist: {A: 0, B: 7, C: 9, D: 20, E: 20, F: 11}
presets:
- id: canonical
label: "Canonical 6-vertex (lazy deletion fires twice)"
input:
nodes: 6
edges: [[0,1,7],[0,2,9],[0,5,14],[1,2,10],[1,3,15],[2,3,11],[2,5,2],[3,4,6],[5,4,9]]
source: 0
- id: sparse
label: "Sparse 5-vertex (no stale entries)"
input:
nodes: 5
edges: [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]
source: 0
- id: dense
label: "Dense 8-vertex (heavy stale-skip pressure)"
input:
nodes: 8
edges: [[0,1,4],[0,2,3],[0,3,7],[1,2,1],[1,4,5],[2,4,2],[2,5,4],[3,5,1],[4,6,3],[5,6,2],[5,7,6],[6,7,2]]
source: 0
n_steps: 27
# Trace generated by instrumenting the verified §2.2 Python reference
#; deterministic re-run produces identical output
#. Two stale-skip events at
# steps 19 and 26 are guaranteed to fire on the canonical input.
keyframes:
- step_id: 0
action: init
state_snapshot:
dist: [0, INF, INF, INF, INF, INF]
pq: [[0, 0]]
settled: [false, false, false, false, false, false]
narration: "dist[A] = 0. Priority queue holds (0, A). All other distances are infinity."
- step_id: 1
action: pop
payload: { node: 0, distance: 0 }
state_snapshot:
dist: [0, INF, INF, INF, INF, INF]
pq: []
settled: [false, false, false, false, false, false]
narration: "Pop (0, A). This is the smallest tentative distance, so A is about to settle."
- step_id: 2
action: settle
payload: { node: 0, distance: 0 }
state_snapshot:
dist: [0, INF, INF, INF, INF, INF]
pq: []
settled: [true, false, false, false, false, false]
narration: "Settle A at distance 0. Its distance is now final; no later relaxation can improve it."
- step_id: 3
action: relaxImprove
payload: { from: 0, to: 1, oldDistance: null, newDistance: 7 }
state_snapshot:
dist: [0, 7, INF, INF, INF, INF]
pq: [[7, 1]]
settled: [true, false, false, false, false, false]
narration: "Edge A->B with weight 7. dist[B] improves from infinity to 7. Push (7, B)."
- step_id: 4
action: relaxImprove
payload: { from: 0, to: 2, oldDistance: null, newDistance: 9 }
state_snapshot:
dist: [0, 7, 9, INF, INF, INF]
pq: [[7, 1], [9, 2]]
settled: [true, false, false, false, false, false]
narration: "Edge A->C with weight 9. dist[C] = 9. Push (9, C)."
- step_id: 5
action: relaxImprove
payload: { from: 0, to: 5, oldDistance: null, newDistance: 14 }
state_snapshot:
dist: [0, 7, 9, INF, INF, 14]
pq: [[7, 1], [9, 2], [14, 5]]
settled: [true, false, false, false, false, false]
narration: "Edge A->F with weight 14. dist[F] = 14. Push (14, F)."
- step_id: 6
action: pop
payload: { node: 1, distance: 7 }
state_snapshot:
dist: [0, 7, 9, INF, INF, 14]
pq: [[9, 2], [14, 5]]
settled: [true, false, false, false, false, false]
narration: "Pop (7, B). The next-smallest tentative distance."
- step_id: 7
action: settle
payload: { node: 1, distance: 7 }
state_snapshot:
dist: [0, 7, 9, INF, INF, 14]
pq: [[9, 2], [14, 5]]
settled: [true, true, false, false, false, false]
narration: "Settle B at distance 7."
- step_id: 8
action: relaxSkip
payload: { from: 1, to: 2, current: 9, candidate: 17 }
state_snapshot:
dist: [0, 7, 9, INF, INF, 14]
pq: [[9, 2], [14, 5]]
settled: [true, true, false, false, false, false]
narration: "Edge B->C: candidate 7 + 10 = 17, but dist[C] is already 9. Skip."
- step_id: 9
action: relaxImprove
payload: { from: 1, to: 3, oldDistance: null, newDistance: 22 }
state_snapshot:
dist: [0, 7, 9, 22, INF, 14]
pq: [[9, 2], [14, 5], [22, 3]]
settled: [true, true, false, false, false, false]
narration: "Edge B->D: dist[D] = 7 + 15 = 22. Push (22, D). This will be improved later."
- step_id: 10
action: pop
payload: { node: 2, distance: 9 }
state_snapshot:
dist: [0, 7, 9, 22, INF, 14]
pq: [[14, 5], [22, 3]]
settled: [true, true, false, false, false, false]
narration: "Pop (9, C)."
- step_id: 11
action: settle
payload: { node: 2, distance: 9 }
state_snapshot:
dist: [0, 7, 9, 22, INF, 14]
pq: [[14, 5], [22, 3]]
settled: [true, true, true, false, false, false]
narration: "Settle C at distance 9."
- step_id: 12
action: relaxImprove
payload: { from: 2, to: 3, oldDistance: 22, newDistance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, INF, 14]
pq: [[14, 5], [20, 3], [22, 3]]
settled: [true, true, true, false, false, false]
narration: "Edge C->D with weight 11: dist[D] improves from 22 to 20. Push (20, D). Now the heap holds TWO entries for D: (20, D) and (22, D). The stale (22, D) will be skipped later."
- step_id: 13
action: relaxImprove
payload: { from: 2, to: 5, oldDistance: 14, newDistance: 11 }
state_snapshot:
dist: [0, 7, 9, 20, INF, 11]
pq: [[11, 5], [14, 5], [20, 3], [22, 3]]
settled: [true, true, true, false, false, false]
narration: "Edge C->F with weight 2: dist[F] improves from 14 to 11. Push (11, F). Heap now also holds two F entries."
- step_id: 14
action: pop
payload: { node: 5, distance: 11 }
state_snapshot:
dist: [0, 7, 9, 20, INF, 11]
pq: [[14, 5], [20, 3], [22, 3]]
settled: [true, true, true, false, false, false]
narration: "Pop (11, F). The fresh entry; the stale (14, F) sits in the heap."
- step_id: 15
action: settle
payload: { node: 5, distance: 11 }
state_snapshot:
dist: [0, 7, 9, 20, INF, 11]
pq: [[14, 5], [20, 3], [22, 3]]
settled: [true, true, true, false, false, true]
narration: "Settle F at distance 11."
- step_id: 16
action: relaxImprove
payload: { from: 5, to: 4, oldDistance: null, newDistance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[14, 5], [20, 3], [20, 4], [22, 3]]
settled: [true, true, true, false, false, true]
narration: "Edge F->E with weight 9: dist[E] = 11 + 9 = 20. Push (20, E)."
- step_id: 17
action: pop
payload: { node: 5, distance: 14 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[20, 3], [20, 4], [22, 3]]
settled: [true, true, true, false, false, true]
narration: "Pop (14, F)."
- step_id: 18
action: staleSkip
payload: { node: 5, poppedDistance: 14, currentDistance: 11 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[20, 3], [20, 4], [22, 3]]
settled: [true, true, true, false, false, true]
narration: "LAZY DELETION FIRES. The popped distance 14 is greater than dist[F] = 11. This entry is stale; F was already settled with a smaller distance. Skip without scanning F's neighbors. This is the work that decrease-key would have avoided in the textbook formulation."
- step_id: 19
action: pop
payload: { node: 3, distance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[20, 4], [22, 3]]
settled: [true, true, true, false, false, true]
narration: "Pop (20, D)."
- step_id: 20
action: settle
payload: { node: 3, distance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[20, 4], [22, 3]]
settled: [true, true, true, true, false, true]
narration: "Settle D at distance 20."
- step_id: 21
action: relaxSkip
payload: { from: 3, to: 4, current: 20, candidate: 26 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[20, 4], [22, 3]]
settled: [true, true, true, true, false, true]
narration: "Edge D->E: candidate 20 + 6 = 26, but dist[E] is already 20. Skip. The path A->C->F->E (cost 20) beat A->C->D->E (cost 26)."
- step_id: 22
action: pop
payload: { node: 4, distance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[22, 3]]
settled: [true, true, true, true, false, true]
narration: "Pop (20, E)."
- step_id: 23
action: settle
payload: { node: 4, distance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: [[22, 3]]
settled: [true, true, true, true, true, true]
narration: "Settle E at distance 20. ALL SIX NODES SETTLED."
- step_id: 24
action: pop
payload: { node: 3, distance: 22 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: []
settled: [true, true, true, true, true, true]
narration: "Pop (22, D). Stale entry left over from B->D relaxation."
- step_id: 25
action: staleSkip
payload: { node: 3, poppedDistance: 22, currentDistance: 20 }
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: []
settled: [true, true, true, true, true, true]
narration: "Second LAZY DELETION. Popped distance 22 > dist[D] = 20. Discard."
- step_id: 26
action: done
payload:
distances: [0, 7, 9, 20, 20, 11]
parents: [null, 0, 0, 2, 5, 2]
state_snapshot:
dist: [0, 7, 9, 20, 20, 11]
pq: []
settled: [true, true, true, true, true, true]
narration: "Priority queue empty. Final distances from A: [A:0, B:7, C:9, D:20, E:20, F:11]. Shortest-path tree: A->B (direct), A->C (direct), A->C->D, A->C->F->E, A->C->F."
notes: |
Three synchronized panels: priority queue (sorted vertical list of
(d, node) tuples on the left), dist[] array (top, with cell-by-cell
animation on relax-improve events), graph (center, Wong palette
for settled / popped-current / candidate / unsettled). Two stale-skip
events at steps 18 and 25 are deterministic and guaranteed on the
canonical input. Reduced-motion fallback uses keyframes [0, 8, 18, 26]
to surface init / mid-run / lazy-deletion-fires / final state.
Default mode: step-through, paused at step 0 (no autoplay; this is
a Level-2 hard-algorithm widget per `widget-decision-rule.md` §1).From The Engineering Handbook (source), CC BY-SA 4.0.