# Dijkstra's Algorithm as a Spreading Frontier

> Dijkstra's algorithm, taught as a frontier that spreads outward from a source across a weighted graph. We build a small six-node graph, give every node a tentative distance, and watch those numbers fall as edges are relaxed and the settled region grows one node at a time. Then we do the part that matters: we prove that the greedy choice — always settling the unsettled node with the smallest tentative distance — is safe, by tracing where any cheaper route would have to go, and showing exactly how that argument collapses the moment a single negative edge appears. We finish with the priority-queue implementation, the predecessor pointers that recover the routes themselves, and the O((V + E) log V) bound.

- Canonical watch page: [Dijkstra's Algorithm as a Spreading Frontier](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier)
- Publisher: [Academa, Inc.](https://academa.ai)
- Subject: Computer Science
- Published: 2026-08-28T23:31:54.000Z
- Updated: 2026-08-28T23:31:54.000Z
- Duration: PT593S (9 minutes 53 seconds)
- Chapters: 3
- Views: 0
- Language: en-US
- Access: Free
- Video stream: [HLS content](https://academa.ai/media/l/01M14TX77JPFEBWST5NE8CZPB8/1/dark/master.m3u8)
- Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TX77JPFEBWST5NE8CZPB8/1/semantic.json)
- Thumbnail: [Image](https://academa.ai/media/l/01M14TX77JPFEBWST5NE8CZPB8/1/dark/poster.jpg)

## Description

Watch Dijkstra's algorithm as a frontier of settled nodes spreading outward, and see why the greedy choice is provably safe.

## Chapters

- [00:00–05:15.774 · The Frontier Spreads](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=0)
- [05:15.774–07:37.875 · Why Settling Is Safe](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125)
- [07:37.875–09:53 · From Frontier to Priority Queue](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333)

## Transcript

### [00:00 · The Frontier Spreads](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=0)

Dijkstra's algorithm finds the cheapest route from one source to every node in a graph. The picture to keep is a filled region that spreads outward, with the edges crossing its boundary forming a live frontier. Here are six nodes. S is the source, and A, B, C, D and E are the other places. The gray connections are weighted edges. Their numbers measure cost, so a path is cheap when the sum of its edge weights is small. The weights are four, two, one, five, eight, ten, two again, six, and three. Every one is non-negative. That condition will carry the proof. This blue patch around S is the settled region we will grow. The two yellow edges leaving it are the frontier. Keep that boundary alive in your eye while the numbers decide which node the patch reaches next. First see why counting edges is not enough. Start at S, then B, then D, then E. This route uses only three edges. The three-hop route pays two, ten, and three. Together those weights total fifteen. The other route goes S, B, A, C, D, E. Its five weights are two, one, five, two, and three. Together they total thirteen. Fifteen is greater than thirteen. More hops can cost less, so every decision must use the accumulated weights rather than the hop count. Each node carries a tentative distance: the cheapest route found so far. Unreached nodes have no number yet. The source is different. Reaching S from S costs zero, so zero is final from the start. Relaxation is the only arithmetic move. On this picture, u is S, v is A, and w of u v is the four on their edge. A route through u costs d of u plus that edge weight. If that new cost is smaller than d of v, then replace d of v with it. The test comes first. The assignment happens only when the test wins. For A, the source contributes zero and the edge contributes four. Together they make four, so A receives four. For B, the source contributes zero and the edge contributes two. Together they make two, so B receives two. Now compare the unsettled rim. A carries four. B carries two. The smallest tentative distance belongs to B, so B is the greedy choice. Relax B to A. B contributes two and the edge contributes one. Together they make three, better than four, so A changes to three. A's predecessor changes from S to B at the same decision. The route record now agrees with the lower value. Next, B contributes two and the edge to C contributes eight. Together they make ten, so C receives ten. For D, B contributes two and the edge contributes ten. Together they make twelve, so D receives twelve. The live rim now reads A at three, C at ten, and D at twelve. Those are the finite candidates touching the blue region. The smallest is A at three. Settle A, grow the blue region, and update the crossing edges around the same weighted graph. Relax A to C. A contributes three and the edge contributes five. Together they make eight, so C falls from ten to eight. Now C has eight, D has twelve, and E is unreached. The smallest is C. Settle C and let the blue region reach it. Relax C to D. C contributes eight and the edge contributes two. Together they make ten, so D drops from twelve to ten immediately. Relax C to E. C contributes eight and the edge contributes six. Together they make fourteen, so E receives fourteen. The rim has D at ten and E at fourteen. Ten is smaller, so D is next. The region grows through D and the yellow boundary moves outward. Relax D to E. D contributes ten and the edge contributes three. Together they make thirteen, so E falls from fourteen to thirteen. Only E remains, carrying thirteen. Settle it. The blue region now covers every node, and no crossing edge remains. Read the final distances directly from the node labels: S zero, B two, A three, C eight, D ten, and E thirteen. The predecessor tree gives the route to E backwards: E to D, D to C, C to A, A to B, and B to S. Reverse that walk and its total is thirteen. The arithmetic explains every update, and the growing region shows every greedy commitment. What remains is to prove why the smallest label on the frontier is safe to make permanent.

### [05:15.774 · Why Settling Is Safe](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125)

Freeze one generic greedy step. The blue polygon is the settled region. Its yellow crossing edges are the frontier, and C carries the smallest tentative distance there: eight. Suppose a cheaper route P to C exists. It begins at S inside the polygon and ends at C outside, so it must cross the frontier for the first time. Call the first unsettled node on that route x. The only part of P we need is the short local prefix from u to x, ending exactly at x. Every edge leaving a settled node was relaxed when that node settled. Therefore the cost already spent along the prefix P sub x cannot be less than the tentative distance written at x. The greedy choice points to C because eight is the smallest frontier label. Since x is also on that frontier, d of x is at least d of C, which is eight. So the proposed cheaper route has already spent at least eight when it reaches x. It still has the remaining segment from x to C ahead of it. Every remaining edge has non-negative weight. Continuing from x cannot reduce the amount already spent, so P cannot reach C for less than eight. That contradiction makes eight final. The same frontier-crossing argument applies at every greedy step, which is why settled labels never need to reopen. Now change only one fact. This three-node graph has S to X of weight one, S to Y of weight four, and a red edge from Y to X of weight minus four. Relaxing S gives X one and Y four. The greedy rule points at X because one is smaller, so it settles X and grows the region there. But the other route walks S to Y and then Y to X. Its two weights are four and minus four. Together they total zero. Zero is smaller than one. The negative edge discounts the route after X was declared final, so the non-negative step in the proof has failed. Dijkstra's algorithm therefore requires non-negative weights. When a graph really contains negative edges, Bellman-Ford is the algorithm to reach for instead.

### [07:37.875 · From Frontier to Priority Queue](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333)

The whole algorithm fits into four numbered steps. The graph is in the state just after B settles: the blue region contains S and B, and its yellow crossing edges form the current frontier. First, initialize the labels; the source gets zero. Second, choose the smallest unsettled label; here A at three is next. Third, relax its outgoing edges. Fourth, repeat while the frontier still has a node. A plain array finds the minimum by scanning every key: three, ten, twelve, infinity. One scan costs V, and V choices give V times V, which is order V squared. A priority queue stores exactly the unsettled rim. Its smallest key is A's three. Pop A, settle it, and let the filled region grow through A. Relaxing A improves C. Decrease C's queue key from ten to eight, and the node label beside C changes to eight with the queue key. Those are the two heap operations Dijkstra needs: pop-min chooses the next settled node, and decrease-key records a better route without scanning the whole graph. Every node is popped once, giving V pop-min operations. Every edge can trigger a decrease-key, giving at most E lowerings. A binary heap makes each operation cost log V. The total is order V plus E, multiplied by log V. Finish the same run. C settles at eight. Its relaxation lowers D to ten. D then settles, which makes E reachable at fourteen. Relaxing D lowers E to thirteen, and E settles last. The blue region grows at each commitment. Each improvement also records a predecessor. The surviving choices form the shortest-path tree: S to B, B to A, A to C, C to D, and D to E. The final state carries the whole algorithm: a filled settled region, the tree that recovers every route, and no frontier edge left to cross. Non-negative weights are what make each greedy step permanent.

## About Academa, Inc.

Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need.

## Complete audiovisual record

Immutable source: [semantic.json](https://academa.ai/media/l/01M14TX77JPFEBWST5NE8CZPB8/1/semantic.json)

Record version: 1. Render attempt: 1.

### How to read this timeline

Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video.

### Scene 1: [The Frontier Spreads](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=0)

Span: 00:00–05:15.774 (0s–315.774125s).

#### Objects

- answers: a Table \[text\] that says "Node $S$ $B$ $A$ $C$ $D$ $E$ Distance 0 2 3 8 10 13 Via start $S$ $B$ $A$ $C$ $D$" (rows=(('Node', '$S$', '$B$', '$A$', '$C$', '$D$', '$E$'), ('Distance…, header=True)
- calc\_ac: an Arithmetic \[text\] that says "$3 5 8$" (operator='+', operands=('3', '5'), result='8')
- calc\_ba: an Arithmetic \[text\] that says "$2 1 3$" (operator='+', operands=('2', '1'), result='3')
- calc\_bc: an Arithmetic \[text\] that says "$2 8 10$" (operator='+', operands=('2', '8'), result='10')
- calc\_bd: an Arithmetic \[text\] that says "$2 10 12$" (operator='+', operands=('2', '10'), result='12')
- calc\_cd: an Arithmetic \[text\] that says "$8 2 10$" (operator='+', operands=('8', '2'), result='10')
- calc\_ce: an Arithmetic \[text\] that says "$8 6 14$" (operator='+', operands=('8', '6'), result='14')
- calc\_de: an Arithmetic \[text\] that says "$10 3 13$" (operator='+', operands=('10', '3'), result='13')
- calc\_sa: an Arithmetic \[text\] that says "$0 4 4$" (operator='+', operands=('0', '4'), result='4')
- calc\_sb: an Arithmetic \[text\] that says "$0 2 2$" (operator='+', operands=('0', '2'), result='2')
- card: a Title that says "Algorithms — Dijkstra's Algorithm as a Spreading Frontier"
- cheap\_route: an Arithmetic \[text\] that says "$2 1 5 2 3 13$" (operator='+', operands=('2', '1', '5', '2', '3'), result='13')
- cost: a Math \[text\] that says "$w(P) = sum\_(e in P) w(e)$"
- d\_a: a VariableNumber (initial\_value=4.0, format\_spec='.0f')
- d\_c: a VariableNumber (initial\_value=10.0, format\_spec='.0f')
- d\_d: a VariableNumber (initial\_value=12.0, format\_spec='.0f')
- d\_e: a VariableNumber (initial\_value=14.0, format\_spec='.0f')
- edge\_ab: a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4))
- edge\_ac: a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9))
- edge\_bc: a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9))
- edge\_bd: a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9))
- edge\_cd: a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9))
- edge\_ce: a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6))
- edge\_de: a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6))
- edge\_sa: a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2))
- edge\_sb: a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4))
- heading\_answers: a Heading that says "The Finished Shortest-Path Tree"
- heading\_routes: a Heading that says "Weighted Paths Need Weighted Reasoning"
- heading\_run: a Heading that says "Settle the Smallest, Then Relax"
- node\_a: a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2))
- node\_a\_live: a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False)
- node\_b: a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4))
- node\_b\_live: a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False)
- node\_c: a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9))
- node\_c\_live: a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False)
- node\_d: a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9))
- node\_d\_live: a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False)
- node\_e: a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6))
- node\_e\_live: a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False)
- node\_s: a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7))
- node\_s\_live: a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False)
- plane: a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4))
- point: a Point \[yellow\] drawn in plane (location=(1.1, 3.7))
- point\_10: a Point \[yellow\] drawn in plane (location=(6.6, 4.9))
- point\_11: a Point \[yellow\] drawn in plane (location=(6.6, 1.9))
- point\_12: a Point \[yellow\] drawn in plane (location=(6.6, 4.9))
- point\_13: a Point \[yellow\] drawn in plane (location=(6.6, 1.9))
- point\_14: a Point \[yellow\] drawn in plane (location=(9.0, 3.6))
- point\_15: a Point \[yellow\] drawn in plane (location=(6.6, 1.9))
- point\_16: a Point \[yellow\] drawn in plane (location=(9.0, 3.6))
- point\_17: a Point \[yellow\] drawn in plane (location=(9.0, 3.6))
- point\_18: a Point \[yellow\] drawn in plane (location=(9.0, 3.6))
- point\_19: a Point \[yellow\] drawn in plane (location=(6.6, 1.9))
- point\_2: a Point \[yellow\] drawn in plane (location=(3.6, 1.4))
- point\_20: a Point \[yellow\] drawn in plane (location=(6.6, 4.9))
- point\_21: a Point \[yellow\] drawn in plane (location=(3.6, 6.2))
- point\_22: a Point \[yellow\] drawn in plane (location=(3.6, 1.4))
- point\_23: a Point \[yellow\] drawn in plane (location=(1.1, 3.7))
- point\_3: a Point \[yellow\] drawn in plane (location=(6.6, 1.9))
- point\_4: a Point \[yellow\] drawn in plane (location=(9.0, 3.6))
- point\_5: a Point \[yellow\] drawn in plane (location=(1.1, 3.7))
- point\_6: a Point \[yellow\] drawn in plane (location=(3.6, 6.2))
- point\_7: a Point \[yellow\] drawn in plane (location=(3.6, 6.2))
- point\_8: a Point \[yellow\] drawn in plane (location=(3.6, 1.4))
- point\_9: a Point \[yellow\] drawn in plane (location=(3.6, 6.2))
- region\_all: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2)
- region\_s: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2)
- region\_sb: a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2)
- region\_sba: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2)
- region\_sbac: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2)
- region\_sbacd: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2)
- relax\_if: a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"
- relax\_then: a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"
- route\_compare: a Math \[text\] that says "$15 \> 13$"
- short\_route: an Arithmetic \[text\] that says "$2 10 3 15$" (operator='+', operands=('2', '10', '3'), result='15')

#### Beats

##### [00:00](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=0)

Narration: Dijkstra's algorithm finds the cheapest route from one source to every node in a graph. The picture to keep is a filled region that spreads outward, with the edges crossing its boundary forming a live frontier.

Board: Empty.

Actions:
- [00:00](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=0): card is shown on the screen, written out.
- [00:1.5](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=1.5): card: enter:write-left-to-right.
- [00:11.366](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=11.366): card is hidden from the screen — left the board.

##### [00:12.566](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=12.565999999999999)

Narration: Here are six nodes. S is the source, and A, B, C, D and E are the other places. The gray connections are weighted edges. Their numbers measure cost, so a path is cheap when the sum of its edge weights is small.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [00:12.566](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=12.565999999999999): heading\_routes is shown on the screen, written out.
- [00:12.566](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=12.565999999999999): plane is shown on the screen, written out.
- [00:15.492](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=15.491999999999999): node\_s is shown on the screen, written out.
- [00:19.045](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=19.044999999999998): node\_a is shown on the screen, written out.
- [00:19.225](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=19.224999999999998): node\_b is shown on the screen, written out.
- [00:19.405](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=19.404999999999998): node\_c is shown on the screen, written out.
- [00:19.585](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=19.584999999999997): node\_d is shown on the screen, written out.
- [00:19.765](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=19.764999999999997): node\_e is shown on the screen, written out.
- [00:20.798](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=20.798): edge\_sa is shown on the screen, drawn.
- [00:20.938](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=20.938): edge\_sb is shown on the screen, drawn.
- [00:21.078](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.078): edge\_ab is shown on the screen, drawn.
- [00:21.218](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.218): edge\_ac is shown on the screen, drawn.
- [00:21.358](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.357999999999997): edge\_bc is shown on the screen, drawn.
- [00:21.498](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.497999999999998): edge\_bd is shown on the screen, drawn.
- [00:21.638](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.637999999999998): edge\_cd is shown on the screen, drawn.
- [00:21.778](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.778): edge\_ce is shown on the screen, drawn.
- [00:21.918](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=21.918): edge\_de is shown on the screen, drawn.
- [00:26.278](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=26.278): plane moves to a new place on the board.
- [00:26.278](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=26.278): cost is shown on the screen, written out.

##### [00:28.898](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=28.898)

Narration: The weights are four, two, one, five, eight, ten, two again, six, and three. Every one is non-negative. That condition will carry the proof.

Board: cost — a Math \[text\] that says "$w(P) = sum\_(e in P) w(e)$"; plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); heading\_routes — a Heading that says "Weighted Paths Need Weighted Reasoning"; node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6))

Actions:
- [00:29.861](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=29.861): edge\_sa is emphasized.
- [00:30.303](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=30.303): edge\_sa is no longer emphasized.
- [00:30.303](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=30.303): edge\_sb is emphasized.
- [00:30.755](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=30.755000000000003): edge\_sb is no longer emphasized.
- [00:30.755](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=30.755000000000003): edge\_ab is emphasized.
- [00:31.103](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=31.103): edge\_ab is no longer emphasized.
- [00:31.103](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=31.103): edge\_ac is emphasized.
- [00:31.556](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=31.556): edge\_ac is no longer emphasized.
- [00:31.556](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=31.556): edge\_bc is emphasized.
- [00:31.869](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=31.869000000000003): edge\_bc is no longer emphasized.
- [00:31.869](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=31.869000000000003): edge\_bd is emphasized.
- [00:32.496](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=32.496): edge\_bd is no longer emphasized.
- [00:32.496](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=32.496): edge\_cd is emphasized.
- [00:33.251](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=33.251000000000005): edge\_cd is no longer emphasized.
- [00:33.251](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=33.251000000000005): edge\_ce is emphasized.
- [00:34.064](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=34.06400000000001): edge\_ce is no longer emphasized.
- [00:34.064](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=34.06400000000001): edge\_de is emphasized.
- [00:38.754](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=38.754): edge\_de is no longer emphasized.

##### [00:39.354](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=39.354)

Narration: This blue patch around S is the settled region we will grow. The two yellow edges leaving it are the frontier. Keep that boundary alive in your eye while the numbers decide which node the patch reaches next.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [00:39.923](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=39.923): region\_s is shown on the screen, faded in.
- [00:43.963](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=43.963): edge\_sa is emphasized.
- [00:43.963](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=43.963): edge\_sb is emphasized.

##### [00:52.4](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=52.4)

Narration: First see why counting edges is not enough. Start at S, then B, then D, then E. This route uses only three edges.

Board: cost — a Math \[text\] that says "$w(P) = sum\_(e in P) w(e)$"; plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); heading\_routes — a Heading that says "Weighted Paths Need Weighted Reasoning"; node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); region\_s — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2)

Actions:
- [00:56.394](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=56.394000000000005): point is shown on the screen, grown.
- [00:56.394](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=56.394000000000005): The segment (1.1, 3.7) to (3.6, 1.4) in plane is lit up.
- [00:57.45](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=57.45): point\_2 is shown on the screen, grown.
- [00:58.394](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=58.394000000000005): point is hidden from the screen.
- [00:58.414](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=58.414): point\_3 is shown on the screen, grown.
- [00:58.414](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=58.414): The segment (3.6, 1.4) to (6.6, 1.9) in plane is lit up.
- [00:59.285](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=59.285000000000004): point\_4 is shown on the screen, grown.
- [00:59.285](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=59.285000000000004): The segment (6.6, 1.9) to (9.0, 3.6) in plane is lit up.
- [00:59.45](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=59.45): point\_2 is hidden from the screen.
- [01:0.414](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=60.414): point\_3 is hidden from the screen.
- [01:1.285](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=61.285000000000004): point\_4 is hidden from the screen.

##### [01:3.483](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=63.4835)

Narration: The three-hop route pays two, ten, and three. Together those weights total fifteen.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [01:5.26](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=65.26): short\_route is shown on the screen, written out.
- [01:5.26](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=65.26): short\_route (the "2" part) is emphasized.
- [01:5.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=65.875): short\_route is shown on the screen, written out.
- [01:5.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=65.875): short\_route (the "2" part) is no longer emphasized.
- [01:5.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=65.875): short\_route (the "10" part) is emphasized.
- [01:6.572](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=66.572): short\_route is shown on the screen, written out.
- [01:6.572](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=66.572): short\_route (the "10" part) is no longer emphasized.
- [01:6.572](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=66.572): short\_route (the "3" part) is emphasized.
- [01:7.501](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=67.501): short\_route is shown on the screen, drawn.
- [01:7.501](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=67.501): short\_route (the "3" part) is no longer emphasized.
- [01:8.301](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=68.301): short\_route is shown on the screen, drawn.
- [01:8.917](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=68.917): short\_route is shown on the screen, written out.

##### [01:10.55](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=70.5505)

Narration: The other route goes S, B, A, C, D, E. Its five weights are two, one, five, two, and three. Together they total thirteen.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [01:11.073](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=71.07300000000001): short\_route is hidden from the screen.
- [01:11.073](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=71.07300000000001): plane: retire a lit segment (unemphasize\_line).
- [01:12.571](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=72.571): The segment (3.6, 1.4) to (3.6, 6.2) in plane is lit up.
- [01:12.872](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=72.872): The segment (3.6, 6.2) to (6.6, 4.9) in plane is lit up.
- [01:13.186](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=73.186): The segment (6.6, 4.9) to (6.6, 1.9) in plane is lit up.
- [01:14.672](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=74.67200000000001): cheap\_route is shown on the screen, written out.
- [01:14.672](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=74.67200000000001): cheap\_route (the "5" part) is emphasized.
- [01:15.403](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=75.403): cheap\_route is shown on the screen, written out.
- [01:15.403](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=75.403): cheap\_route (the "2" part) is emphasized.
- [01:15.403](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=75.403): cheap\_route (the "5" part) is no longer emphasized.
- [01:16.03](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=76.03): cheap\_route is shown on the screen, written out.
- [01:16.03](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=76.03): cheap\_route (the "2" part) is no longer emphasized.
- [01:16.03](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=76.03): cheap\_route (the "1" part) is emphasized.
- [01:16.901](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=76.90100000000001): cheap\_route is shown on the screen, written out.
- [01:16.901](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=76.90100000000001): cheap\_route (the "1" part) is no longer emphasized.
- [01:16.901](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=76.90100000000001): cheap\_route (the "2" part) is emphasized.
- [01:17.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=77.447): cheap\_route is shown on the screen, written out.
- [01:17.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=77.447): cheap\_route (the "2" part) is no longer emphasized.
- [01:17.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=77.447): cheap\_route (the "3" part) is emphasized.
- [01:18.631](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=78.631): cheap\_route is shown on the screen, drawn.
- [01:18.631](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=78.631): cheap\_route (the "3" part) is no longer emphasized.
- [01:19.431](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=79.431): cheap\_route is shown on the screen, drawn.
- [01:19.595](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=79.595): cheap\_route is shown on the screen, written out.

##### [01:21.286](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=81.286)

Narration: Fifteen is greater than thirteen. More hops can cost less, so every decision must use the accumulated weights rather than the hop count.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [01:21.634](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=81.634): route\_compare is shown on the screen, written out.
- [01:21.634](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=81.634): route\_compare (the "15" part) is emphasized.
- [01:22.784](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=82.784): route\_compare (the "13" part) is emphasized.
- [01:22.784](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=82.784): route\_compare (the "15" part) is no longer emphasized.
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): cheap\_route is hidden from the screen — left the board.
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): cost is hidden from the screen — left the board.
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): heading\_routes is hidden from the screen — left the board.
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): route\_compare is hidden from the screen — left the board.
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): route\_compare (the "13" part) is no longer emphasized.
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): plane: retire a lit segment (unemphasize\_line).
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): plane: retire a lit segment (unemphasize\_line).
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): plane: retire a lit segment (unemphasize\_line).
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): plane: retire a lit segment (unemphasize\_line).
- [01:30.133](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.13250000000001): plane: retire a lit segment (unemphasize\_line).

##### [01:30.733](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.7325)

Narration: Each node carries a tentative distance: the cheapest route found so far. Unreached nodes have no number yet. The source is different. Reaching S from S costs zero, so zero is final from the start.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); region\_s — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2)

Actions:
- [01:30.733](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=90.7325): heading\_run is shown on the screen, written out.
- [01:42.412](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=102.412): node\_s\_live is shown on the screen, written out.
- [01:43.886](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=103.886): node\_s is indicated — a transient flash.

##### [01:45.85](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=105.85)

Narration: Relaxation is the only arithmetic move. On this picture, u is S, v is A, and w of u v is the four on their edge. A route through u costs d of u plus that edge weight.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); region\_s — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2); heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False)

Actions:
- [01:50.872](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=110.872): point\_5 is shown on the screen, grown.
- [01:51.893](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=111.893): point\_6 is shown on the screen, grown.
- [01:52.872](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=112.872): point\_5 is hidden from the screen.
- [01:53.893](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=113.893): point\_6 is hidden from the screen.
- [01:54.111](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=114.11099999999999): edge\_sa is indicated — a transient flash.

##### [02:0.103](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=120.103)

Narration: If that new cost is smaller than d of v, then replace d of v with it. The test comes first. The assignment happens only when the test wins.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [02:0.434](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=120.434): relax\_if is shown on the screen, written out.
- [02:0.434](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=120.434): relax\_if (the "upright("if")" part) is emphasized.
- [02:2.628](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=122.628): relax\_then is shown on the screen, written out.
- [02:2.628](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=122.628): relax\_if (the "upright("if")" part) is no longer emphasized.
- [02:2.628](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=122.628): relax\_then (the "upright("then")" part) is emphasized.
- [02:9.803](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=129.80349999999999): relax\_then (the "upright("then")" part) is no longer emphasized.

##### [02:10.404](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=130.4035)

Narration: For A, the source contributes zero and the edge contributes four. Together they make four, so A receives four.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); region\_s — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False)

Actions:
- [02:12.725](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=132.72500000000002): calc\_sa is shown on the screen, written out.
- [02:12.725](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=132.72500000000002): calc\_sa (the "0" part) is emphasized.
- [02:14.49](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=134.49): calc\_sa is shown on the screen, written out.
- [02:14.49](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=134.49): calc\_sa (the "0" part) is no longer emphasized.
- [02:14.49](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=134.49): calc\_sa (the "4" part) is emphasized.
- [02:15.628](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=135.628): calc\_sa is shown on the screen, drawn.
- [02:15.628](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=135.628): calc\_sa (the "4" part) is no longer emphasized.
- [02:16.428](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=136.42799999999997): calc\_sa is shown on the screen, drawn.
- [02:16.522](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=136.522): node\_a\_live is shown on the screen, written out.
- [02:16.522](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=136.522): calc\_sa is shown on the screen, written out.
- [02:17.578](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=137.57800000000003): edge\_sa is indicated — a transient flash.

##### [02:19.397](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=139.39700000000002)

Narration: For B, the source contributes zero and the edge contributes two. Together they make two, so B receives two.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); region\_s — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False)

Actions:
- [02:19.397](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=139.39700000000002): calc\_sa is hidden from the screen.
- [02:21.034](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=141.03400000000002): calc\_sb is shown on the screen, written out.
- [02:21.034](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=141.03400000000002): calc\_sb (the "0" part) is emphasized.
- [02:22.706](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=142.70600000000002): calc\_sb is shown on the screen, written out.
- [02:22.706](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=142.70600000000002): calc\_sb (the "0" part) is no longer emphasized.
- [02:22.706](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=142.70600000000002): calc\_sb (the "2" part) is emphasized.
- [02:23.74](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=143.74): calc\_sb is shown on the screen, drawn.
- [02:23.74](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=143.74): calc\_sb (the "2" part) is no longer emphasized.
- [02:24.529](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=144.52900000000002): node\_b\_live is shown on the screen, written out.
- [02:24.529](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=144.52900000000002): calc\_sb is shown on the screen, written out.
- [02:24.54](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=144.54): calc\_sb is shown on the screen, drawn.
- [02:25.504](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=145.50400000000002): edge\_sb is indicated — a transient flash.

##### [02:27.26](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=147.25950000000003)

Narration: Now compare the unsettled rim. A carries four. B carries two. The smallest tentative distance belongs to B, so B is the greedy choice.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); region\_s — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.35), (1.1, 4.35), (1.8, 3.35)), fill\_opacity=0.2); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False)

Actions:
- [02:30.795](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=150.79500000000004): point\_7 is shown on the screen, grown.
- [02:32.559](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=152.55900000000005): point\_8 is shown on the screen, grown.
- [02:32.795](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=152.79500000000004): point\_7 is hidden from the screen.
- [02:33.825](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=153.82500000000005): node\_b is indicated — a transient flash.
- [02:34.559](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=154.55900000000005): point\_8 is hidden from the screen.
- [02:37.412](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=157.41200000000003): region\_s becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2).
- [02:37.412](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=157.41200000000003): edge\_sb is no longer emphasized.
- [02:37.412](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=157.41200000000003): edge\_ab is emphasized.
- [02:37.412](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=157.41200000000003): edge\_bc is emphasized.
- [02:37.412](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=157.41200000000003): edge\_bd is emphasized.

##### [02:38.704](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=158.70350000000002)

Narration: Relax B to A. B contributes two and the edge contributes one. Together they make three, better than four, so A changes to three.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2)

Actions:
- [02:38.704](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=158.70350000000002): calc\_sb is hidden from the screen.
- [02:41.321](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=161.32100000000003): calc\_ba is shown on the screen, written out.
- [02:41.321](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=161.32100000000003): calc\_ba (the "2" part) is emphasized.
- [02:42.935](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=162.93500000000003): calc\_ba is shown on the screen, written out.
- [02:42.935](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=162.93500000000003): calc\_ba (the "2" part) is no longer emphasized.
- [02:42.935](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=162.93500000000003): calc\_ba (the "1" part) is emphasized.
- [02:43.736](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=163.73600000000002): calc\_ba is shown on the screen, drawn.
- [02:43.736](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=163.73600000000002): calc\_ba (the "1" part) is no longer emphasized.
- [02:44.536](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=164.536): calc\_ba is shown on the screen, drawn.
- [02:44.549](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=164.54900000000004): node\_a\_live is redrawn as the numbers it depends on change.
- [02:44.549](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=164.54900000000004): calc\_ba is shown on the screen, written out.
- [02:44.549](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=164.54900000000004): d\_a ticks to 3.0.

##### [02:48.957](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=168.95700000000002)

Narration: A's predecessor changes from S to B at the same decision. The route record now agrees with the lower value.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [02:50.327](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=170.32700000000003): edge\_sa is indicated — a transient flash.
- [02:50.327](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=170.32700000000003): edge\_ab is indicated — a transient flash.

##### [02:56.732](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=176.7315)

Narration: Next, B contributes two and the edge to C contributes eight. Together they make ten, so C receives ten.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [02:56.732](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=176.7315): calc\_ba is hidden from the screen.
- [02:58.078](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=178.078): calc\_bc is shown on the screen, written out.
- [02:58.078](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=178.078): calc\_bc (the "2" part) is emphasized.
- [03:0.052](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=180.05200000000002): calc\_bc is shown on the screen, written out.
- [03:0.052](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=180.05200000000002): calc\_bc (the "2" part) is no longer emphasized.
- [03:0.052](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=180.05200000000002): calc\_bc (the "8" part) is emphasized.
- [03:0.993](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=180.99300000000002): calc\_bc is shown on the screen, drawn.
- [03:0.993](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=180.99300000000002): calc\_bc (the "8" part) is no longer emphasized.
- [03:1.793](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=181.793): calc\_bc is shown on the screen, drawn.
- [03:1.852](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=181.852): node\_c\_live is shown on the screen, written out.
- [03:1.852](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=181.852): calc\_bc is shown on the screen, written out.
- [03:2.92](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=182.92000000000002): edge\_bc is indicated — a transient flash.

##### [03:4.797](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=184.79700000000003)

Narration: For D, B contributes two and the edge contributes ten. Together they make twelve, so D receives twelve.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False)

Actions:
- [03:4.797](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=184.79700000000003): calc\_bc is hidden from the screen.
- [03:6.538](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=186.538): calc\_bd is shown on the screen, written out.
- [03:6.538](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=186.538): calc\_bd (the "2" part) is emphasized.
- [03:8.222](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=188.222): calc\_bd is shown on the screen, written out.
- [03:8.222](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=188.222): calc\_bd (the "2" part) is no longer emphasized.
- [03:8.222](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=188.222): calc\_bd (the "10" part) is emphasized.
- [03:9.267](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=189.267): calc\_bd is shown on the screen, drawn.
- [03:9.267](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=189.267): calc\_bd (the "10" part) is no longer emphasized.
- [03:10.067](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=190.06699999999998): calc\_bd is shown on the screen, drawn.
- [03:10.115](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=190.115): node\_d\_live is shown on the screen, written out.
- [03:10.115](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=190.115): calc\_bd is shown on the screen, written out.
- [03:11.206](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=191.20600000000002): edge\_bd is indicated — a transient flash.

##### [03:13.211](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=193.211)

Narration: The live rim now reads A at three, C at ten, and D at twelve. Those are the finite candidates touching the blue region.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False)

Actions:
- [03:15.347](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=195.347): point\_9 is shown on the screen, grown.
- [03:16.253](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=196.25300000000001): point\_10 is shown on the screen, grown.
- [03:17.347](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=197.347): point\_9 is hidden from the screen.
- [03:17.448](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=197.448): point\_11 is shown on the screen, grown.
- [03:18.253](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=198.25300000000001): point\_10 is hidden from the screen.
- [03:19.448](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=199.448): point\_11 is hidden from the screen.

##### [03:21.863](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=201.8625)

Narration: The smallest is A at three. Settle A, grow the blue region, and update the crossing edges around the same weighted graph.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [03:23.528](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=203.528): node\_a is indicated — a transient flash.
- [03:25.63](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=205.63): region\_s becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2).
- [03:27.453](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=207.453): edge\_sa is no longer emphasized.
- [03:27.453](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=207.453): edge\_ab is no longer emphasized.
- [03:27.453](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=207.453): edge\_ac is emphasized.

##### [03:30.619](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=210.6185)

Narration: Relax A to C. A contributes three and the edge contributes five. Together they make eight, so C falls from ten to eight.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2)

Actions:
- [03:30.619](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=210.6185): calc\_bd is hidden from the screen.
- [03:33.579](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=213.57900000000004): calc\_ac is shown on the screen, written out.
- [03:33.579](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=213.57900000000004): calc\_ac (the "3" part) is emphasized.
- [03:35.239](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=215.23900000000003): calc\_ac is shown on the screen, written out.
- [03:35.239](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=215.23900000000003): calc\_ac (the "3" part) is no longer emphasized.
- [03:35.239](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=215.23900000000003): calc\_ac (the "5" part) is emphasized.
- [03:36.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=216.44700000000003): calc\_ac is shown on the screen, drawn.
- [03:36.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=216.44700000000003): calc\_ac (the "5" part) is no longer emphasized.
- [03:37.247](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=217.247): calc\_ac is shown on the screen, drawn.
- [03:37.492](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=217.49200000000002): node\_c\_live is redrawn as the numbers it depends on change.
- [03:37.492](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=217.49200000000002): calc\_ac is shown on the screen, written out.
- [03:37.492](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=217.49200000000002): d\_c ticks to 8.0.
- [03:38.653](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=218.65300000000002): edge\_bc is indicated — a transient flash.
- [03:38.653](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=218.65300000000002): edge\_ac is indicated — a transient flash.

##### [03:40.844](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=220.8435)

Narration: Now C has eight, D has twelve, and E is unreached. The smallest is C. Settle C and let the blue region reach it.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [03:42.097](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=222.09700000000004): point\_12 is shown on the screen, grown.
- [03:43.27](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=223.27): point\_13 is shown on the screen, grown.
- [03:44.097](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=224.09700000000004): point\_12 is hidden from the screen.
- [03:44.245](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=224.24500000000003): point\_14 is shown on the screen, grown.
- [03:45.27](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=225.27): point\_13 is hidden from the screen.
- [03:46.245](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=226.24500000000003): point\_14 is hidden from the screen.
- [03:46.358](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=226.358): node\_c is indicated — a transient flash.
- [03:49.69](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=229.69000000000003): region\_s becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2).
- [03:49.69](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=229.69000000000003): edge\_ac is no longer emphasized.
- [03:49.69](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=229.69000000000003): edge\_bc is no longer emphasized.
- [03:49.69](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=229.69000000000003): edge\_cd is emphasized.
- [03:49.69](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=229.69000000000003): edge\_ce is emphasized.

##### [03:51.12](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=231.1205)

Narration: Relax C to D. C contributes eight and the edge contributes two. Together they make ten, so D drops from twelve to ten immediately.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2)

Actions:
- [03:51.12](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=231.1205): calc\_ac is hidden from the screen.
- [03:54.098](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=234.09799999999998): calc\_cd is shown on the screen, written out.
- [03:54.098](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=234.09799999999998): calc\_cd (the "8" part) is emphasized.
- [03:55.724](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=235.724): calc\_cd is shown on the screen, written out.
- [03:55.724](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=235.724): calc\_cd (the "8" part) is no longer emphasized.
- [03:55.724](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=235.724): calc\_cd (the "2" part) is emphasized.
- [03:56.954](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=236.95399999999998): calc\_cd is shown on the screen, drawn.
- [03:56.954](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=236.95399999999998): calc\_cd (the "2" part) is no longer emphasized.
- [03:57.754](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=237.75399999999996): calc\_cd is shown on the screen, drawn.
- [03:57.837](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=237.837): node\_d\_live is redrawn as the numbers it depends on change.
- [03:57.837](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=237.837): calc\_cd is shown on the screen, written out.
- [03:57.837](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=237.837): d\_d ticks to 10.0.
- [03:59.032](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=239.03199999999998): edge\_bd is indicated — a transient flash.
- [03:59.032](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=239.03199999999998): edge\_cd is indicated — a transient flash.

##### [04:2.198](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=242.1985)

Narration: Relax C to E. C contributes eight and the edge contributes six. Together they make fourteen, so E receives fourteen.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [04:2.198](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=242.1985): calc\_cd is hidden from the screen.
- [04:5.124](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=245.12400000000002): calc\_ce is shown on the screen, written out.
- [04:5.124](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=245.12400000000002): calc\_ce (the "8" part) is emphasized.
- [04:6.761](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=246.76100000000002): calc\_ce is shown on the screen, written out.
- [04:6.761](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=246.76100000000002): calc\_ce (the "8" part) is no longer emphasized.
- [04:6.761](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=246.76100000000002): calc\_ce (the "6" part) is emphasized.
- [04:8.084](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=248.084): calc\_ce is shown on the screen, drawn.
- [04:8.084](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=248.084): calc\_ce (the "6" part) is no longer emphasized.
- [04:8.884](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=248.884): calc\_ce is shown on the screen, drawn.
- [04:8.897](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=248.89700000000002): node\_e\_live is shown on the screen, written out.
- [04:8.897](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=248.89700000000002): calc\_ce is shown on the screen, written out.
- [04:10.081](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=250.08100000000002): edge\_ce is indicated — a transient flash.

##### [04:12.063](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=252.0625)

Narration: The rim has D at ten and E at fourteen. Ten is smaller, so D is next. The region grows through D and the yellow boundary moves outward.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2); node\_e\_live — a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False)

Actions:
- [04:13.467](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=253.467): point\_15 is shown on the screen, grown.
- [04:14.768](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=254.768): point\_16 is shown on the screen, grown.
- [04:15.467](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=255.467): point\_15 is hidden from the screen.
- [04:16.544](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=256.544): node\_d is indicated — a transient flash.
- [04:16.768](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=256.76800000000003): point\_16 is hidden from the screen.
- [04:19.168](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=259.168): region\_s becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2).
- [04:20.654](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=260.654): edge\_bd is no longer emphasized.
- [04:20.654](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=260.654): edge\_cd is no longer emphasized.
- [04:20.654](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=260.654): edge\_de is emphasized.

##### [04:22.891](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=262.891)

Narration: Relax D to E. D contributes ten and the edge contributes three. Together they make thirteen, so E falls from fourteen to thirteen.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); relax\_if — a Math \[text\] that says "$upright("if") quad d\[u\] + w(u, v) \< d\[v\]$"; relax\_then — a Math \[text\] that says "$upright("then") quad d\[v\] arrow.l d\[u\] + w(u, v)$"; heading\_run — a Heading that says "Settle the Smallest, Then Relax"; node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2); node\_e\_live — a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False); region\_sbacd — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2)

Actions:
- [04:22.891](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=262.891): calc\_ce is hidden from the screen.
- [04:25.851](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=265.851): calc\_de is shown on the screen, written out.
- [04:25.851](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=265.851): calc\_de (the "10" part) is emphasized.
- [04:27.337](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=267.337): calc\_de is shown on the screen, written out.
- [04:27.337](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=267.337): calc\_de (the "10" part) is no longer emphasized.
- [04:27.337](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=267.337): calc\_de (the "3" part) is emphasized.
- [04:28.44](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=268.44000000000005): calc\_de is shown on the screen, drawn.
- [04:28.44](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=268.44000000000005): calc\_de (the "3" part) is no longer emphasized.
- [04:29.24](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=269.24000000000007): calc\_de is shown on the screen, drawn.
- [04:29.3](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=269.3): node\_e\_live is redrawn as the numbers it depends on change.
- [04:29.3](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=269.3): calc\_de is shown on the screen, written out.
- [04:29.3](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=269.3): d\_e ticks to 13.0.
- [04:30.635](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=270.635): edge\_ce is indicated — a transient flash.
- [04:30.635](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=270.635): edge\_de is indicated — a transient flash.

##### [04:33.406](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=273.4055)

Narration: Only E remains, carrying thirteen. Settle it. The blue region now covers every node, and no crossing edge remains.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [04:35.577](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=275.57700000000006): point\_17 is shown on the screen, grown.
- [04:36.97](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=276.97): node\_e is indicated — a transient flash.
- [04:37.577](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=277.57700000000006): point\_17 is hidden from the screen.
- [04:38.909](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=278.90900000000005): region\_s becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2).
- [04:40.429](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=280.42900000000003): edge\_ce is no longer emphasized.
- [04:40.429](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=280.42900000000003): edge\_de is no longer emphasized.
- [04:42.252](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.2525): calc\_de is hidden from the screen.
- [04:42.252](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.2525): heading\_run is hidden from the screen — left the board.
- [04:42.252](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.2525): relax\_if is hidden from the screen — left the board.
- [04:42.252](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.2525): relax\_then is hidden from the screen — left the board.

##### [04:42.853](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.8525)

Narration: Read the final distances directly from the node labels: S zero, B two, A three, C eight, D ten, and E thirteen.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2); node\_e\_live — a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False); region\_sbacd — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2); region\_all — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2)

Actions:
- [04:42.853](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.8525): heading\_answers is shown on the screen, written out.
- [04:42.853](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=282.8525): answers is shown on the screen, written out.
- [04:46.637](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=286.637): node\_s\_live is emphasized.
- [04:47.299](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=287.29900000000004): node\_s\_live is no longer emphasized.
- [04:47.299](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=287.29900000000004): node\_b\_live is emphasized.
- [04:48.042](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=288.04200000000003): node\_b\_live is no longer emphasized.
- [04:48.042](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=288.04200000000003): node\_a\_live is emphasized.
- [04:48.75](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=288.75): node\_a\_live is no longer emphasized.
- [04:48.75](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=288.75): node\_c\_live is emphasized.
- [04:49.54](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=289.54): node\_c\_live is no longer emphasized.
- [04:49.54](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=289.54): node\_d\_live is emphasized.
- [04:50.724](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=290.724): node\_d\_live is no longer emphasized.
- [04:50.724](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=290.724): node\_e\_live is emphasized.

##### [04:52.415](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=292.415)

Narration: The predecessor tree gives the route to E backwards: E to D, D to C, C to A, A to B, and B to S. Reverse that walk and its total is thirteen.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s\_live — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); node\_a\_live — a Point \[text\] labelled "4" drawn in plane (location=(3.6, 6.2), show\_marker=False); node\_b\_live — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); node\_c\_live — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); node\_d\_live — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2); node\_e\_live — a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False); region\_sbacd — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2); region\_all — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2); answers — a Table \[text\] that says "Node $S$ $B$ $A$ $C$ $D$ $E$ Distance 0 2 3 8 10 13 Via start $S$ $B$ $A$ $C$ $D$" (rows=(('Node', '$S$', '$B$', '$A$', '$C$', '$D$', '$E$'), ('Distance…, header=True); heading\_answers — a Heading that says "The Finished Shortest-Path Tree"

Actions:
- [04:52.415](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=292.415): node\_e\_live is no longer emphasized.
- [04:56.13](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=296.13000000000005): point\_18 is shown on the screen, grown.
- [04:56.56](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=296.56000000000006): point\_19 is shown on the screen, grown.
- [04:56.56](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=296.56000000000006): The segment (6.6, 1.9) to (9.0, 3.6) in plane is lit up.
- [04:57.245](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=297.24500000000006): point\_20 is shown on the screen, grown.
- [04:57.245](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=297.24500000000006): The segment (6.6, 4.9) to (6.6, 1.9) in plane is lit up.
- [04:57.988](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=297.98800000000006): point\_21 is shown on the screen, grown.
- [04:57.988](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=297.98800000000006): The segment (3.6, 6.2) to (6.6, 4.9) in plane is lit up.
- [04:58.13](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=298.13000000000005): point\_18 is hidden from the screen.
- [04:58.56](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=298.56000000000006): point\_19 is hidden from the screen.
- [04:58.661](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=298.66100000000006): point\_22 is shown on the screen, grown.
- [04:58.661](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=298.66100000000006): The segment (3.6, 1.4) to (3.6, 6.2) in plane is lit up.
- [04:59.245](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=299.24500000000006): point\_20 is hidden from the screen.
- [04:59.451](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=299.451): point\_23 is shown on the screen, grown.
- [04:59.451](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=299.451): The segment (1.1, 3.7) to (3.6, 1.4) in plane is lit up.
- [04:59.988](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=299.98800000000006): point\_21 is hidden from the screen.
- [05:0.661](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=300.66100000000006): point\_22 is hidden from the screen.
- [05:1.451](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=301.451): point\_23 is hidden from the screen.

##### [05:4.51](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=304.5095)

Narration: The arithmetic explains every update, and the growing region shows every greedy commitment. What remains is to prove why the smallest label on the frontier is safe to make permanent.

Board: Unchanged from the preceding beat in this scene.

Actions:
- None.

### Scene 2: [Why Settling Is Safe](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125)

Span: 05:15.774–07:37.875 (315.774125s–457.8747708333333s).

#### Objects

- bound: a Derivation \[text\] that says "$w(P\_x) &\>= d\[x\] \\ &\>= d\[C\] = 8$"
- claim: a Math \[text\] that says "$d\[C\] = 8 quad upright("is final")$"
- frontier\_uc: a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(8.7, 3.2))
- frontier\_ux: a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0))
- frontier\_vx: a Line \[gray\] drawn in proof (start=(3.5, 1.5), end=(6.1, 4.0))
- heading\_negative: a Heading that says "One Negative Edge Breaks the Proof"
- heading\_proof: a Heading that says "Why the Greedy Step Is Safe"
- inside\_su: a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.4, 4.7))
- inside\_sv: a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.5, 1.5))
- neg: a Figure (x\_range=(0.0, 6.4), y\_range=(0.0, 4.4), aspect=(6.4, 4.4))
- neg\_region\_s: a Polygon \[blue\] drawn in neg (vertices=((0.35, 1.8), (1.05, 3.0), (1.75, 1.8)), fill\_opacity=0.22)
- neg\_region\_sx: a Polygon \[blue\] drawn in neg (vertices=((0.3, 1.8), (0.8, 2.85), (4.45, 4.05), (5.3, 3.5), (4.55, 2.8)), fill\_opacity=0.22)
- neg\_s: a Point \[text\] labelled "S: 0" drawn in neg (location=(1.0, 2.2))
- neg\_sx: a Line \[gray\] labelled "1" drawn in neg (start=(1.0, 2.2), end=(4.7, 3.45))
- neg\_sy: a Line \[gray\] labelled "4" drawn in neg (start=(1.0, 2.2), end=(4.7, 0.85))
- neg\_x: a Point \[text\] labelled "X" drawn in neg (location=(4.7, 3.45))
- neg\_x\_live: a Point \[text\] labelled "1" drawn in neg (location=(4.7, 3.45), show\_marker=False)
- neg\_y: a Point \[text\] labelled "Y" drawn in neg (location=(4.7, 0.85))
- neg\_y\_live: a Point \[text\] labelled "4" drawn in neg (location=(4.7, 0.85), show\_marker=False)
- neg\_yx: a Line \[red\] labelled "-4" drawn in neg (start=(4.7, 0.85), end=(4.7, 3.45))
- negative\_compare: a Math \[text\] that says "$0 \< 1$"
- negative\_lesson: a Math \[text\] that says "$w(e) \< 0 quad arrow.r quad upright("use Bellman-Ford")$"
- negative\_total: an Arithmetic \[text\] that says "$4 -4 0$" (operator='+', operands=('4', '-4'), result='0')
- nonnegative: a Math \[text\] that says "$w(e) \>= 0$"
- point: a Point \[yellow\] drawn in proof (location=(8.7, 3.2))
- point\_10: a Point \[yellow\] drawn in neg (location=(4.7, 3.45))
- point\_11: a Point \[yellow\] drawn in neg (location=(1.0, 2.2))
- point\_12: a Point \[yellow\] drawn in neg (location=(4.7, 0.85))
- point\_13: a Point \[yellow\] drawn in neg (location=(4.7, 3.45))
- point\_2: a Point \[yellow\] drawn in proof (location=(1.0, 3.2))
- point\_3: a Point \[yellow\] drawn in proof (location=(8.7, 3.2))
- point\_4: a Point \[yellow\] drawn in proof (location=(3.4, 4.7))
- point\_5: a Point \[yellow\] drawn in proof (location=(6.1, 4.0))
- point\_6: a Point \[yellow\] drawn in proof (location=(8.7, 3.2))
- point\_7: a Point \[yellow\] drawn in proof (location=(6.1, 4.0))
- point\_8: a Point \[yellow\] drawn in proof (location=(6.1, 4.0))
- point\_9: a Point \[yellow\] drawn in proof (location=(8.7, 3.2))
- prefix: a Line \[red\] labelled "$P\_x$" drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0))
- proof: a Figure (x\_range=(0.0, 10.0), y\_range=(0.0, 6.5), aspect=(10.0, 6.5))
- proof\_c: a Point \[text\] labelled "C: 8" drawn in proof (location=(8.7, 3.2))
- proof\_s: a Point \[text\] labelled "S: 0" drawn in proof (location=(1.0, 3.2))
- proof\_u: a Point \[text\] labelled "u" drawn in proof (location=(3.4, 4.7))
- proof\_v: a Point \[text\] labelled "upright("settled")" drawn in proof (location=(3.5, 1.5))
- proof\_x: a Point \[text\] labelled "x: 10" drawn in proof (location=(6.1, 4.0))
- remaining\_xc: a Line \[gray\] labelled "upright("remainder")" drawn in proof (start=(6.1, 4.0), end=(8.7, 3.2))
- settled\_region: a Polygon \[blue\] drawn in proof (vertices=((0.35, 3.2), (2.8, 0.7), (4.2, 1.0), (4.15, 5.25), (2.8, 5.75)), fill\_opacity=0.22)

#### Beats

##### [05:15.774](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125)

Narration: Freeze one generic greedy step. The blue polygon is the settled region. Its yellow crossing edges are the frontier, and C carries the smallest tentative distance there: eight.

Board: Empty.

Actions:
- [05:15.774](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125): heading\_proof is shown on the screen, written out.
- [05:15.774](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125): proof is shown on the screen, written out.
- [05:15.774](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125): inside\_su is shown on the screen, drawn.
- [05:15.774](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=315.774125): proof\_s is shown on the screen, written out.
- [05:18.723](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=318.72312500000004): settled\_region is shown on the screen, faded in.
- [05:19.861](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=319.861125): inside\_sv is shown on the screen, drawn.
- [05:19.861](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=319.861125): proof\_u is shown on the screen, written out.
- [05:19.861](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=319.861125): proof\_v is shown on the screen, written out.
- [05:21.602](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=321.602125): frontier\_ux is shown on the screen, drawn.
- [05:21.602](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=321.602125): frontier\_uc is shown on the screen, drawn.
- [05:21.602](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=321.602125): frontier\_vx is shown on the screen, drawn.
- [05:21.602](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=321.602125): frontier\_ux is emphasized.
- [05:21.602](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=321.602125): frontier\_uc is emphasized.
- [05:21.602](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=321.602125): frontier\_vx is emphasized.
- [05:23.053](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=323.053125): proof\_x is shown on the screen, written out.
- [05:23.053](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=323.053125): remaining\_xc is shown on the screen, drawn.
- [05:24.238](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=324.238125): proof\_c is shown on the screen, written out.
- [05:24.238](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=324.238125): point is shown on the screen, grown.
- [05:26.238](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=326.238125): point is hidden from the screen.
- [05:27.407](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=327.407125): proof moves to a new place on the board.
- [05:27.407](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=327.407125): claim is shown on the screen, written out.

##### [05:28.762](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=328.762125)

Narration: Suppose a cheaper route P to C exists. It begins at S inside the polygon and ends at C outside, so it must cross the frontier for the first time.

Board: claim — a Math \[text\] that says "$d\[C\] = 8 quad upright("is final")$"; proof — a Figure (x\_range=(0.0, 10.0), y\_range=(0.0, 6.5), aspect=(10.0, 6.5)); heading\_proof — a Heading that says "Why the Greedy Step Is Safe"; settled\_region — a Polygon \[blue\] drawn in proof (vertices=((0.35, 3.2), (2.8, 0.7), (4.2, 1.0), (4.15, 5.25), (2.8, 5.75)), fill\_opacity=0.22); inside\_su — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.4, 4.7)); inside\_sv — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.5, 1.5)); proof\_s — a Point \[text\] labelled "S: 0" drawn in proof (location=(1.0, 3.2)); proof\_u — a Point \[text\] labelled "u" drawn in proof (location=(3.4, 4.7)); proof\_v — a Point \[text\] labelled "upright("settled")" drawn in proof (location=(3.5, 1.5)); proof\_x — a Point \[text\] labelled "x: 10" drawn in proof (location=(6.1, 4.0)); proof\_c — a Point \[text\] labelled "C: 8" drawn in proof (location=(8.7, 3.2)); frontier\_ux — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0)); frontier\_uc — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(8.7, 3.2)); frontier\_vx — a Line \[gray\] drawn in proof (start=(3.5, 1.5), end=(6.1, 4.0)); remaining\_xc — a Line \[gray\] labelled "upright("remainder")" drawn in proof (start=(6.1, 4.0), end=(8.7, 3.2))

Actions:
- [05:30.689](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=330.68912500000005): point\_3 is shown on the screen, grown.
- [05:32.689](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=332.68912500000005): point\_3 is hidden from the screen.
- [05:33.093](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=333.09312500000004): point\_2 is shown on the screen, grown.
- [05:33.429](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=333.429125): settled\_region is indicated — a transient flash.
- [05:35.093](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=335.09312500000004): point\_2 is hidden from the screen.
- [05:37.296](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=337.296125): point\_4 is shown on the screen, grown.
- [05:39.296](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=339.296125): point\_4 is hidden from the screen.

##### [05:40.125](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=340.12462500000004)

Narration: Call the first unsettled node on that route x. The only part of P we need is the short local prefix from u to x, ending exactly at x.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [05:43.062](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=343.06212500000004): point\_5 is shown on the screen, grown.
- [05:45.062](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=345.06212500000004): point\_5 is hidden from the screen.
- [05:46.069](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=346.06912500000004): prefix is shown on the screen, drawn.

##### [05:51.197](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=351.197125)

Narration: Every edge leaving a settled node was relaxed when that node settled. Therefore the cost already spent along the prefix P sub x cannot be less than the tentative distance written at x.

Board: claim — a Math \[text\] that says "$d\[C\] = 8 quad upright("is final")$"; proof — a Figure (x\_range=(0.0, 10.0), y\_range=(0.0, 6.5), aspect=(10.0, 6.5)); heading\_proof — a Heading that says "Why the Greedy Step Is Safe"; settled\_region — a Polygon \[blue\] drawn in proof (vertices=((0.35, 3.2), (2.8, 0.7), (4.2, 1.0), (4.15, 5.25), (2.8, 5.75)), fill\_opacity=0.22); inside\_su — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.4, 4.7)); inside\_sv — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.5, 1.5)); proof\_s — a Point \[text\] labelled "S: 0" drawn in proof (location=(1.0, 3.2)); proof\_u — a Point \[text\] labelled "u" drawn in proof (location=(3.4, 4.7)); proof\_v — a Point \[text\] labelled "upright("settled")" drawn in proof (location=(3.5, 1.5)); proof\_x — a Point \[text\] labelled "x: 10" drawn in proof (location=(6.1, 4.0)); proof\_c — a Point \[text\] labelled "C: 8" drawn in proof (location=(8.7, 3.2)); frontier\_ux — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0)); frontier\_uc — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(8.7, 3.2)); frontier\_vx — a Line \[gray\] drawn in proof (start=(3.5, 1.5), end=(6.1, 4.0)); remaining\_xc — a Line \[gray\] labelled "upright("remainder")" drawn in proof (start=(6.1, 4.0), end=(8.7, 3.2)); prefix — a Line \[red\] labelled "$P\_x$" drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0))

Actions:
- [05:51.928](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=351.928125): prefix is indicated — a transient flash.
- [05:52.59](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=352.59012500000006): proof\_u is indicated — a transient flash.
- [05:55.678](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=355.678125): bound is shown on the screen, written out.
- [05:58.198](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=358.198125): bound (the "w(P\_x)" part) is emphasized.
- [05:59.614](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=359.61412500000006): bound (the "d\[x\]" part) is emphasized.
- [05:59.614](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=359.61412500000006): bound (the "w(P\_x)" part) is no longer emphasized.

##### [06:4.208](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=364.208125)

Narration: The greedy choice points to C because eight is the smallest frontier label. Since x is also on that frontier, d of x is at least d of C, which is eight.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [06:5.787](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=365.78712500000006): point\_6 is shown on the screen, grown.
- [06:7.787](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=367.78712500000006): point\_6 is hidden from the screen.
- [06:9.236](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=369.236125): bound is shown on the screen, written out.
- [06:9.7](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=369.700125): point\_7 is shown on the screen, grown.
- [06:11.7](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=371.700125): point\_7 is hidden from the screen.
- [06:13.311](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=373.31112500000006): bound (the "d\[x\]" part) is no longer emphasized.
- [06:13.311](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=373.31112500000006): bound (the "d\[C\]" part) is emphasized.
- [06:13.949](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=373.94912500000004): bound (the "8" part) is emphasized.
- [06:13.949](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=373.94912500000004): bound (the "d\[C\]" part) is no longer emphasized.

##### [06:15.293](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=375.29262500000004)

Narration: So the proposed cheaper route has already spent at least eight when it reaches x. It still has the remaining segment from x to C ahead of it.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [06:19.797](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=379.79712500000005): point\_8 is shown on the screen, grown.
- [06:21.654](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=381.654125): remaining\_xc is emphasized.
- [06:21.797](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=381.79712500000005): point\_8 is hidden from the screen.
- [06:23.094](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=383.094125): point\_9 is shown on the screen, grown.

##### [06:24.948](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=384.948125)

Narration: Every remaining edge has non-negative weight. Continuing from x cannot reduce the amount already spent, so P cannot reach C for less than eight.

Board: claim — a Math \[text\] that says "$d\[C\] = 8 quad upright("is final")$"; proof — a Figure (x\_range=(0.0, 10.0), y\_range=(0.0, 6.5), aspect=(10.0, 6.5)); heading\_proof — a Heading that says "Why the Greedy Step Is Safe"; settled\_region — a Polygon \[blue\] drawn in proof (vertices=((0.35, 3.2), (2.8, 0.7), (4.2, 1.0), (4.15, 5.25), (2.8, 5.75)), fill\_opacity=0.22); inside\_su — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.4, 4.7)); inside\_sv — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.5, 1.5)); proof\_s — a Point \[text\] labelled "S: 0" drawn in proof (location=(1.0, 3.2)); proof\_u — a Point \[text\] labelled "u" drawn in proof (location=(3.4, 4.7)); proof\_v — a Point \[text\] labelled "upright("settled")" drawn in proof (location=(3.5, 1.5)); proof\_x — a Point \[text\] labelled "x: 10" drawn in proof (location=(6.1, 4.0)); proof\_c — a Point \[text\] labelled "C: 8" drawn in proof (location=(8.7, 3.2)); frontier\_ux — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0)); frontier\_uc — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(8.7, 3.2)); frontier\_vx — a Line \[gray\] drawn in proof (start=(3.5, 1.5), end=(6.1, 4.0)); remaining\_xc — a Line \[gray\] labelled "upright("remainder")" drawn in proof (start=(6.1, 4.0), end=(8.7, 3.2)); prefix — a Line \[red\] labelled "$P\_x$" drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0)); point\_9 — a Point \[yellow\] drawn in proof (location=(8.7, 3.2))

Actions:
- [06:25.094](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=385.094125): point\_9 is hidden from the screen.
- [06:26.62](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=386.62012500000003): nonnegative is shown on the screen, written out.
- [06:26.62](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=386.62012500000003): nonnegative (the "0" part) is emphasized.
- [06:28.338](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=388.338125): remaining\_xc is indicated — a transient flash.
- [06:35.095](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=395.09512500000005): nonnegative (the "0" part) is no longer emphasized.

##### [06:35.695](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=395.695125)

Narration: That contradiction makes eight final. The same frontier-crossing argument applies at every greedy step, which is why settled labels never need to reopen.

Board: claim — a Math \[text\] that says "$d\[C\] = 8 quad upright("is final")$"; nonnegative — a Math \[text\] that says "$w(e) \>= 0$"; proof — a Figure (x\_range=(0.0, 10.0), y\_range=(0.0, 6.5), aspect=(10.0, 6.5)); heading\_proof — a Heading that says "Why the Greedy Step Is Safe"; settled\_region — a Polygon \[blue\] drawn in proof (vertices=((0.35, 3.2), (2.8, 0.7), (4.2, 1.0), (4.15, 5.25), (2.8, 5.75)), fill\_opacity=0.22); inside\_su — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.4, 4.7)); inside\_sv — a Line \[gray\] drawn in proof (start=(1.0, 3.2), end=(3.5, 1.5)); proof\_s — a Point \[text\] labelled "S: 0" drawn in proof (location=(1.0, 3.2)); proof\_u — a Point \[text\] labelled "u" drawn in proof (location=(3.4, 4.7)); proof\_v — a Point \[text\] labelled "upright("settled")" drawn in proof (location=(3.5, 1.5)); proof\_x — a Point \[text\] labelled "x: 10" drawn in proof (location=(6.1, 4.0)); proof\_c — a Point \[text\] labelled "C: 8" drawn in proof (location=(8.7, 3.2)); frontier\_ux — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0)); frontier\_uc — a Line \[gray\] drawn in proof (start=(3.4, 4.7), end=(8.7, 3.2)); frontier\_vx — a Line \[gray\] drawn in proof (start=(3.5, 1.5), end=(6.1, 4.0)); remaining\_xc — a Line \[gray\] labelled "upright("remainder")" drawn in proof (start=(6.1, 4.0), end=(8.7, 3.2)); prefix — a Line \[red\] labelled "$P\_x$" drawn in proof (start=(3.4, 4.7), end=(6.1, 4.0))

Actions:
- [06:37.634](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=397.63412500000004): proof\_c is indicated — a transient flash.
- [06:37.634](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=397.63412500000004): claim (the "upright("is final")" part) is emphasized.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): bound is hidden from the screen — left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): claim is hidden from the screen — left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): heading\_proof is hidden from the screen — left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): nonnegative is hidden from the screen — left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): proof is hidden from the screen — left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): settled\_region is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): inside\_su is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): inside\_sv is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): proof\_s is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): proof\_u is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): proof\_v is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): proof\_x is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): proof\_c is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): frontier\_ux is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): frontier\_uc is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): frontier\_vx is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): remaining\_xc is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): prefix is hidden from the screen — proof left the board.
- [06:45.076](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.07612500000005): claim (the "upright("is final")" part) is no longer emphasized.

##### [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125)

Narration: Now change only one fact. This three-node graph has S to X of weight one, S to Y of weight four, and a red edge from Y to X of weight minus four.

Board: Empty.

Actions:
- [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125): heading\_negative is shown on the screen, written out.
- [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125): neg is shown on the screen, written out.
- [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125): neg\_region\_s is shown on the screen, faded in.
- [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125): neg\_s is shown on the screen, written out.
- [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125): neg\_x is shown on the screen, written out.
- [06:45.676](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=405.676125): neg\_y is shown on the screen, written out.
- [06:46.965](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=406.965125): neg\_sx is shown on the screen, drawn.
- [06:46.965](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=406.965125): neg\_sx is emphasized.
- [06:53.037](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=413.037125): neg\_sy is shown on the screen, drawn.
- [06:53.037](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=413.037125): neg\_sx is no longer emphasized.
- [06:53.037](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=413.037125): neg\_sy is emphasized.
- [06:54.035](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=414.035125): neg\_yx is shown on the screen, drawn.
- [06:54.035](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=414.035125): neg\_sy is no longer emphasized.
- [06:55.753](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=415.753125): neg\_yx is emphasized.
- [06:56.915](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=416.914625): neg\_yx is no longer emphasized.

##### [06:57.515](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=417.514625)

Narration: Relaxing S gives X one and Y four. The greedy rule points at X because one is smaller, so it settles X and grows the region there.

Board: neg — a Figure (x\_range=(0.0, 6.4), y\_range=(0.0, 4.4), aspect=(6.4, 4.4)); heading\_negative — a Heading that says "One Negative Edge Breaks the Proof"; neg\_region\_s — a Polygon \[blue\] drawn in neg (vertices=((0.35, 1.8), (1.05, 3.0), (1.75, 1.8)), fill\_opacity=0.22); neg\_s — a Point \[text\] labelled "S: 0" drawn in neg (location=(1.0, 2.2)); neg\_x — a Point \[text\] labelled "X" drawn in neg (location=(4.7, 3.45)); neg\_y — a Point \[text\] labelled "Y" drawn in neg (location=(4.7, 0.85)); neg\_sx — a Line \[gray\] labelled "1" drawn in neg (start=(1.0, 2.2), end=(4.7, 3.45)); neg\_sy — a Line \[gray\] labelled "4" drawn in neg (start=(1.0, 2.2), end=(4.7, 0.85)); neg\_yx — a Line \[red\] labelled "-4" drawn in neg (start=(4.7, 0.85), end=(4.7, 3.45))

Actions:
- [06:59.186](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=419.186125): point\_10 is shown on the screen, grown.
- [06:59.511](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=419.511125): neg\_x\_live is shown on the screen, written out.
- [07:0.196](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=420.196125): neg\_y\_live is shown on the screen, written out.
- [07:1.186](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=421.186125): point\_10 is hidden from the screen.
- [07:3.633](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=423.633125): neg\_x is indicated — a transient flash.
- [07:5.699](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=425.699125): neg\_region\_s becomes a Polygon \[blue\] drawn in neg (vertices=((0.3, 1.8), (0.8, 2.85), (4.45, 4.05), (5.3, 3.5), (4.55, 2.8)), fill\_opacity=0.22).

##### [07:7.821](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=427.820625)

Narration: But the other route walks S to Y and then Y to X. Its two weights are four and minus four. Together they total zero.

Board: neg — a Figure (x\_range=(0.0, 6.4), y\_range=(0.0, 4.4), aspect=(6.4, 4.4)); heading\_negative — a Heading that says "One Negative Edge Breaks the Proof"; neg\_s — a Point \[text\] labelled "S: 0" drawn in neg (location=(1.0, 2.2)); neg\_x — a Point \[text\] labelled "X" drawn in neg (location=(4.7, 3.45)); neg\_y — a Point \[text\] labelled "Y" drawn in neg (location=(4.7, 0.85)); neg\_sx — a Line \[gray\] labelled "1" drawn in neg (start=(1.0, 2.2), end=(4.7, 3.45)); neg\_sy — a Line \[gray\] labelled "4" drawn in neg (start=(1.0, 2.2), end=(4.7, 0.85)); neg\_yx — a Line \[red\] labelled "-4" drawn in neg (start=(4.7, 0.85), end=(4.7, 3.45)); neg\_x\_live — a Point \[text\] labelled "1" drawn in neg (location=(4.7, 3.45), show\_marker=False); neg\_y\_live — a Point \[text\] labelled "4" drawn in neg (location=(4.7, 0.85), show\_marker=False); neg\_region\_sx — a Polygon \[blue\] drawn in neg (vertices=((0.3, 1.8), (0.8, 2.85), (4.45, 4.05), (5.3, 3.5), (4.55, 2.8)), fill\_opacity=0.22)

Actions:
- [07:9.33](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=429.330125): point\_11 is shown on the screen, grown.
- [07:9.782](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=429.782125): point\_12 is shown on the screen, grown.
- [07:9.782](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=429.782125): neg\_sy is emphasized.
- [07:10.85](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=430.85012500000005): point\_13 is shown on the screen, grown.
- [07:10.85](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=430.85012500000005): neg\_yx is emphasized.
- [07:11.33](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=431.330125): point\_11 is hidden from the screen.
- [07:11.782](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=431.782125): point\_12 is hidden from the screen.
- [07:12.65](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=432.650125): neg moves to a new place on the board.
- [07:12.65](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=432.650125): negative\_total is shown on the screen, written out.
- [07:12.65](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=432.650125): negative\_total (the "4" part) is emphasized.
- [07:12.85](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=432.85012500000005): point\_13 is hidden from the screen.
- [07:13.196](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=433.196125): negative\_total is shown on the screen, written out.
- [07:13.196](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=433.196125): negative\_total (the "4" part) is no longer emphasized.
- [07:13.196](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=433.196125): negative\_total (the "-4" part) is emphasized.
- [07:14.368](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=434.368125): negative\_total is shown on the screen, drawn.
- [07:14.368](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=434.368125): negative\_total (the "-4" part) is no longer emphasized.
- [07:15.168](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=435.16812500000003): negative\_total is shown on the screen, drawn.
- [07:15.599](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=435.599125): negative\_total is shown on the screen, written out.

##### [07:17.046](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=437.046125)

Narration: Zero is smaller than one. The negative edge discounts the route after X was declared final, so the non-negative step in the proof has failed.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [07:17.348](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=437.348125): negative\_compare is shown on the screen, written out.
- [07:17.348](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=437.348125): negative\_compare (the "0" part) is emphasized.
- [07:18.416](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=438.416125): negative\_compare (the "0" part) is no longer emphasized.
- [07:18.416](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=438.416125): negative\_compare (the "1" part) is emphasized.
- [07:19.96](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=439.960125): neg\_yx is indicated — a transient flash.
- [07:26.787](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=446.787125): negative\_compare (the "1" part) is no longer emphasized.

##### [07:27.387](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=447.38712499999997)

Narration: Dijkstra's algorithm therefore requires non-negative weights. When a graph really contains negative edges, Bellman-Ford is the algorithm to reach for instead.

Board: negative\_compare — a Math \[text\] that says "$0 \< 1$"; neg — a Figure (x\_range=(0.0, 6.4), y\_range=(0.0, 4.4), aspect=(6.4, 4.4)); heading\_negative — a Heading that says "One Negative Edge Breaks the Proof"; neg\_s — a Point \[text\] labelled "S: 0" drawn in neg (location=(1.0, 2.2)); neg\_x — a Point \[text\] labelled "X" drawn in neg (location=(4.7, 3.45)); neg\_y — a Point \[text\] labelled "Y" drawn in neg (location=(4.7, 0.85)); neg\_sx — a Line \[gray\] labelled "1" drawn in neg (start=(1.0, 2.2), end=(4.7, 3.45)); neg\_sy — a Line \[gray\] labelled "4" drawn in neg (start=(1.0, 2.2), end=(4.7, 0.85)); neg\_yx — a Line \[red\] labelled "-4" drawn in neg (start=(4.7, 0.85), end=(4.7, 3.45)); neg\_x\_live — a Point \[text\] labelled "1" drawn in neg (location=(4.7, 3.45), show\_marker=False); neg\_y\_live — a Point \[text\] labelled "4" drawn in neg (location=(4.7, 0.85), show\_marker=False); neg\_region\_sx — a Polygon \[blue\] drawn in neg (vertices=((0.3, 1.8), (0.8, 2.85), (4.45, 4.05), (5.3, 3.5), (4.55, 2.8)), fill\_opacity=0.22)

Actions:
- [07:27.387](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=447.38712499999997): neg\_sy is no longer emphasized.
- [07:27.387](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=447.38712499999997): neg\_yx is no longer emphasized.
- [07:33.227](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=453.227125): negative\_lesson is shown on the screen, written out.
- [07:34.446](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=454.446125): negative\_lesson (the "upright("use Bellman-Ford")" part) is emphasized.

### Scene 3: [From Frontier to Priority Queue](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333)

Span: 07:37.875–09:53.465 (457.8747708333333s–593.4649999999999s).

#### Objects

- cost: a Derivation \[text\] that says "$upright("work") &= V dot upright("pop-min") + E dot upright("decrease-key") \\ &= O((V + E) log V)$"
- d\_c: a VariableNumber (initial\_value=10.0, format\_spec='.0f')
- d\_d: a VariableNumber (initial\_value=12.0, format\_spec='.0f')
- d\_e: a VariableNumber (initial\_value=14.0, format\_spec='.0f')
- edge\_ab: a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4))
- edge\_ac: a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9))
- edge\_bc: a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9))
- edge\_bd: a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9))
- edge\_cd: a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9))
- edge\_ce: a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6))
- edge\_de: a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6))
- edge\_sa: a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2))
- edge\_sb: a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4))
- heading\_cost: a Heading that says "Heap Cost and the Route Tree"
- heading\_queue: a Heading that says "The Frontier as a Changing Queue"
- heading\_steps: a Heading that says "The Algorithm, in Order"
- node\_a: a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2))
- node\_b: a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4))
- node\_c: a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9))
- node\_d: a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9))
- node\_e: a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6))
- node\_s: a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7))
- plane: a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4))
- point: a Point \[yellow\] drawn in plane (location=(3.6, 6.2))
- point\_2: a Point \[yellow\] drawn in plane (location=(3.6, 6.2))
- point\_3: a Point \[yellow\] drawn in plane (location=(6.6, 4.9))
- point\_4: a Point \[yellow\] drawn in plane (location=(6.6, 4.9))
- point\_5: a Point \[yellow\] drawn in plane (location=(6.6, 1.9))
- point\_6: a Point \[yellow\] drawn in plane (location=(9.0, 3.6))
- queue\_0: a Table \[text\] that says "Node Key $A$ 3 $C$ 10 $D$ 12 $E$ $infinity$" (rows=(('Node', 'Key'), ('$A$', '3'), ('$C$', '10'), ('$D$', '12'), (…, header=True)
- queue\_1: a Table \[text\] that says "Node Key $C$ 10 $D$ 12 $E$ $infinity$" (rows=(('Node', 'Key'), ('$C$', '10'), ('$D$', '12'), ('$E$', '$infin…, header=True)
- queue\_2: a Table \[text\] that says "Node Key $C$ 8 $D$ 12 $E$ $infinity$" (rows=(('Node', 'Key'), ('$C$', '8'), ('$D$', '12'), ('$E$', '$infini…, header=True)
- region\_all: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2)
- region\_sb: a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2)
- region\_sba: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2)
- region\_sbac: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2)
- region\_sbacd: a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2)
- scan\_array: a Table \[text\] that says "$A$ $C$ $D$ $E$ 3 10 12 $infinity$" (rows=(('$A$', '$C$', '$D$', '$E$'), ('3', '10', '12', '$infinity$')))
- scan\_cost: a Math \[text\] that says "$V dot V = O(V^2)$"
- steps: a Block \[text\] that says "Set $d\[S\] = 0$; leave every other node unreached. Choose and settle the unsettled node with smallest $d$. Relax every edge leaving that node and record predecessors. Repeat while an unsettled reachable node remains."
- tree\_statement: a Math \[text\] that says "$upright("predecessors") arrow.r upright("shortest-path tree")$"
- value\_a: a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False)
- value\_b: a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False)
- value\_c: a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False)
- value\_d: a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False)
- value\_e: a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False)
- value\_s: a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False)

#### Beats

##### [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333)

Narration: The whole algorithm fits into four numbered steps. The graph is in the state just after B settles: the blue region contains S and B, and its yellow crossing edges form the current frontier.

Board: Empty.

Actions:
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): heading\_steps is shown on the screen, written out.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): plane is shown on the screen, written out.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_sa is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_sb is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_ab is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_ac is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_bc is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_bd is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_cd is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_ce is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): edge\_de is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): node\_s is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): node\_a is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): node\_b is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): node\_c is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): node\_d is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): node\_e is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): value\_s is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): value\_a is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): value\_b is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): value\_c is shown on the screen, faded in.
- [07:37.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=457.8747708333333): value\_d is shown on the screen, faded in.
- [07:39.489](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=459.48877083333326): plane moves to a new place on the board.
- [07:39.489](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=459.48877083333326): steps is shown on the screen, written out.
- [07:44.829](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=464.8287708333333): region\_sb is shown on the screen, faded in.
- [07:47.523](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=467.5227708333333): edge\_sa is emphasized.
- [07:47.523](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=467.5227708333333): edge\_ab is emphasized.
- [07:47.523](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=467.5227708333333): edge\_bc is emphasized.
- [07:47.523](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=467.5227708333333): edge\_bd is emphasized.

##### [07:50.967](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=470.96727083333326)

Narration: First, initialize the labels; the source gets zero. Second, choose the smallest unsettled label; here A at three is next. Third, relax its outgoing edges. Fourth, repeat while the frontier still has a node.

Board: steps — a Block \[text\] that says "Set $d\[S\] = 0$; leave every other node unreached. Choose and settle the unsettled node with smallest $d$. Relax every edge leaving that node and record predecessors. Repeat while an unsettled reachable node remains."; plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); heading\_steps — a Heading that says "The Algorithm, in Order"; region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False)

Actions:
- [07:51.316](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=471.31577083333326): steps (the "Set" part) is emphasized.
- [07:54.206](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=474.2057708333333): node\_s is indicated — a transient flash.
- [07:55.297](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=475.2967708333333): steps (the "Choose" part) is emphasized.
- [07:55.297](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=475.2967708333333): steps (the "Set" part) is no longer emphasized.
- [07:59.047](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=479.0467708333333): point is shown on the screen, grown.
- [08:0.592](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=480.59177083333327): steps (the "Choose" part) is no longer emphasized.
- [08:0.592](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=480.59177083333327): steps (the "Relax" part) is emphasized.
- [08:1.047](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=481.0467708333333): point is hidden from the screen.
- [08:1.915](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=481.9147708333333): edge\_ab is indicated — a transient flash.
- [08:1.915](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=481.9147708333333): edge\_ac is indicated — a transient flash.
- [08:3.68](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=483.6797708333333): steps (the "Relax" part) is no longer emphasized.
- [08:3.68](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=483.6797708333333): steps (the "Repeat" part) is emphasized.
- [08:5.27](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=485.26977083333327): region\_sb is indicated — a transient flash.

##### [08:7.629](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=487.6292708333333)

Narration: A plain array finds the minimum by scanning every key: three, ten, twelve, infinity. One scan costs V, and V choices give V times V, which is order V squared.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [08:8.436](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=488.43577083333327): scan\_array is shown on the screen, written out.
- [08:9.771](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=489.7707708333333): scan\_array is shown on the screen, written out.
- [08:11.478](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=491.4777708333333): scan\_array (the "3" part) is emphasized.
- [08:11.954](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=491.9537708333333): scan\_array (the "10" part) is emphasized.
- [08:11.954](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=491.9537708333333): scan\_array (the "3" part) is no longer emphasized.
- [08:12.372](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=492.3717708333333): scan\_array (the "10" part) is no longer emphasized.
- [08:12.372](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=492.3717708333333): scan\_array (the "12" part) is emphasized.
- [08:12.825](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=492.8247708333333): scan\_array (the "$infinity$" part) is emphasized.
- [08:12.825](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=492.8247708333333): scan\_array (the "12" part) is no longer emphasized.
- [08:16.877](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=496.8767708333333): scan\_cost is shown on the screen, written out.
- [08:16.877](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=496.8767708333333): scan\_cost (the "V dot V" part) is emphasized.
- [08:18.618](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=498.6177708333333): scan\_cost (the "O(V^2)" part) is emphasized.
- [08:18.618](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=498.6177708333333): scan\_cost (the "V dot V" part) is no longer emphasized.
- [08:19.471](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=499.4712708333333): heading\_steps is hidden from the screen — left the board.
- [08:19.471](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=499.4712708333333): scan\_array is hidden from the screen — left the board.
- [08:19.471](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=499.4712708333333): scan\_cost is hidden from the screen — left the board.
- [08:19.471](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=499.4712708333333): steps is hidden from the screen — left the board.

##### [08:20.071](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.0712708333333)

Narration: A priority queue stores exactly the unsettled rim. Its smallest key is A's three. Pop A, settle it, and let the filled region grow through A.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); region\_sb — a Polygon \[blue\] drawn in plane (vertices=((0.45, 4.1), (0.55, 3.15), (3.15, 0.7), (4.25, 0.95), (4.2, 2.…, fill\_opacity=0.2); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False)

Actions:
- [08:20.071](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.0712708333333): heading\_queue is shown on the screen, written out.
- [08:20.071](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.0712708333333): queue\_0 is shown on the screen, written out.
- [08:20.191](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.1912708333333): queue\_0 is shown on the screen, written out.
- [08:20.311](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.3112708333333): queue\_0 is shown on the screen, written out.
- [08:20.431](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.4312708333333): queue\_0 is shown on the screen, written out.
- [08:20.551](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=500.55127083333326): queue\_0 is shown on the screen, written out.
- [08:25.755](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=505.7547708333333): point\_2 is shown on the screen, grown.
- [08:25.755](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=505.7547708333333): queue\_0 (the "3" part) is emphasized.
- [08:26.927](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=506.9267708333333): queue\_0 is hidden from the screen.
- [08:26.927](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=506.9267708333333): queue\_1 is shown on the screen, written out.
- [08:27.636](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=507.63577083333325): region\_sb becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2).
- [08:27.755](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=507.7547708333333): point\_2 is hidden from the screen.
- [08:29.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=509.4467708333333): edge\_sa is no longer emphasized.
- [08:29.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=509.4467708333333): edge\_ab is no longer emphasized.
- [08:29.447](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=509.4467708333333): edge\_ac is emphasized.

##### [08:31.259](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=511.2592708333333)

Narration: Relaxing A improves C. Decrease C's queue key from ten to eight, and the node label beside C changes to eight with the queue key.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); queue\_1 — a Table \[text\] that says "Node Key $C$ 10 $D$ 12 $E$ $infinity$" (rows=(('Node', 'Key'), ('$C$', '10'), ('$D$', '12'), ('$E$', '$infin…, header=True); heading\_queue — a Heading that says "The Frontier as a Changing Queue"; region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2)

Actions:
- [08:32.682](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=512.6817708333333): edge\_bc is indicated — a transient flash.
- [08:32.682](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=512.6817708333333): edge\_ac is indicated — a transient flash.
- [08:35.561](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=515.5607708333333): point\_3 is shown on the screen, grown.
- [08:35.956](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=515.9557708333333): value\_c is redrawn as the numbers it depends on change.
- [08:35.956](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=515.9557708333333): queue\_1 is hidden from the screen.
- [08:35.956](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=515.9557708333333): queue\_2 is shown on the screen, written out.
- [08:35.956](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=515.9557708333333): d\_c ticks to 8.0.
- [08:37.561](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=517.5607708333333): point\_3 is hidden from the screen.

##### [08:40.921](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=520.9212708333333)

Narration: Those are the two heap operations Dijkstra needs: pop-min chooses the next settled node, and decrease-key records a better route without scanning the whole graph.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); queue\_2 — a Table \[text\] that says "Node Key $C$ 8 $D$ 12 $E$ $infinity$" (rows=(('Node', 'Key'), ('$C$', '8'), ('$D$', '12'), ('$E$', '$infini…, header=True); heading\_queue — a Heading that says "The Frontier as a Changing Queue"; region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2)

Actions:
- [08:47.84](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=527.8397708333333): node\_c is indicated — a transient flash.
- [08:50.139](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=530.1387708333333): plane moves to a new place on the board.
- [08:50.139](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=530.1387708333333): heading\_queue is hidden from the screen — left the board.
- [08:50.139](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=530.1387708333333): queue\_2 is hidden from the screen — left the board.

##### [08:50.739](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=530.7387708333333)

Narration: Every node is popped once, giving V pop-min operations. Every edge can trigger a decrease-key, giving at most E lowerings.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2)

Actions:
- [08:50.739](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=530.7387708333333): heading\_cost is shown on the screen, written out.
- [08:51.714](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=531.7137708333333): cost is shown on the screen, written out.
- [08:53.096](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=533.0957708333333): cost (the "V dot upright("pop-min")" part) is emphasized.
- [08:58.599](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=538.5987708333333): cost (the "E dot upright("decrease-key")" part) is emphasized.
- [08:58.599](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=538.5987708333333): cost (the "V dot upright("pop-min")" part) is no longer emphasized.

##### [09:0.372](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=540.3717708333332)

Narration: A binary heap makes each operation cost log V. The total is order V plus E, multiplied by log V.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); heading\_cost — a Heading that says "Heap Cost and the Route Tree"

Actions:
- [09:4.122](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=544.1217708333332): cost is shown on the screen, written out.
- [09:4.645](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=544.6447708333333): cost (the "E dot upright("decrease-key")" part) is no longer emphasized.
- [09:4.645](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=544.6447708333333): cost (the "O((V + E) log V)" part) is emphasized.
- [09:7.686](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=547.6862708333333): cost (the "O((V + E) log V)" part) is no longer emphasized.

##### [09:8.286](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=548.2862708333333)

Narration: Finish the same run. C settles at eight. Its relaxation lowers D to ten. D then settles, which makes E reachable at fourteen. Relaxing D lowers E to thirteen, and E settles last. The blue region grows at each commitment.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [09:10.562](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=550.5617708333333): region\_sb becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2).
- [09:10.562](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=550.5617708333333): edge\_ac is no longer emphasized.
- [09:10.562](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=550.5617708333333): edge\_bc is no longer emphasized.
- [09:10.562](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=550.5617708333333): edge\_cd is emphasized.
- [09:10.562](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=550.5617708333333): edge\_ce is emphasized.
- [09:11.085](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=551.0847708333333): point\_4 is shown on the screen, grown.
- [09:13.085](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=553.0847708333333): point\_4 is hidden from the screen.
- [09:13.824](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=553.8237708333332): value\_d is redrawn as the numbers it depends on change.
- [09:13.824](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=553.8237708333332): point\_5 is shown on the screen, grown.
- [09:13.824](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=553.8237708333332): d\_d ticks to 10.0.
- [09:15.438](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=555.4377708333333): region\_sb becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2).
- [09:15.438](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=555.4377708333333): edge\_bd is no longer emphasized.
- [09:15.438](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=555.4377708333333): edge\_cd is no longer emphasized.
- [09:15.438](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=555.4377708333333): edge\_de is emphasized.
- [09:15.824](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=555.8237708333332): point\_5 is hidden from the screen.
- [09:17.528](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=557.5277708333333): value\_e is shown on the screen, written out.
- [09:20.338](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=560.3377708333333): value\_e is redrawn as the numbers it depends on change.
- [09:20.338](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=560.3377708333333): point\_6 is shown on the screen, grown.
- [09:20.338](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=560.3377708333333): d\_e ticks to 13.0.
- [09:21.557](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=561.5567708333333): region\_sb becomes a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2).
- [09:21.557](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=561.5567708333333): edge\_ce is no longer emphasized.
- [09:21.557](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=561.5567708333333): edge\_de is no longer emphasized.
- [09:22.338](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=562.3377708333333): point\_6 is hidden from the screen.

##### [09:25.918](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=565.9182708333333)

Narration: Each improvement also records a predecessor. The surviving choices form the shortest-path tree: S to B, B to A, A to C, C to D, and D to E.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); heading\_cost — a Heading that says "Heap Cost and the Route Tree"; region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2); region\_sbacd — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2); value\_e — a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False); region\_all — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2)

Actions:
- [09:28.009](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=568.0087708333333): tree\_statement is shown on the screen, written out.
- [09:32.653](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=572.6527708333333): The segment (1.1, 3.7) to (3.6, 1.4) in plane is lit up.
- [09:33.767](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=573.7667708333333): The segment (3.6, 1.4) to (3.6, 6.2) in plane is lit up.
- [09:35.033](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=575.0327708333333): The segment (3.6, 6.2) to (6.6, 4.9) in plane is lit up.
- [09:36.031](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=576.0307708333332): The segment (6.6, 4.9) to (6.6, 1.9) in plane is lit up.
- [09:37.308](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=577.3077708333333): The segment (6.6, 1.9) to (9.0, 3.6) in plane is lit up.

##### [09:38.999](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=578.9992708333333)

Narration: The final state carries the whole algorithm: a filled settled region, the tree that recovers every route, and no frontier edge left to cross. Non-negative weights are what make each greedy step permanent.

Board: plane — a Figure (x\_range=(0.0, 10.4), y\_range=(0.0, 7.4), aspect=(10.4, 7.4)); edge\_sa — a Line \[gray\] labelled "4" drawn in plane (start=(1.1, 3.7), end=(3.6, 6.2)); edge\_sb — a Line \[gray\] labelled "2" drawn in plane (start=(1.1, 3.7), end=(3.6, 1.4)); edge\_ab — a Line \[gray\] labelled "1" drawn in plane (start=(3.6, 6.2), end=(3.6, 1.4)); edge\_ac — a Line \[gray\] labelled "5" drawn in plane (start=(3.6, 6.2), end=(6.6, 4.9)); edge\_bc — a Line \[gray\] labelled "8" drawn in plane (start=(3.6, 1.4), end=(6.6, 4.9)); edge\_bd — a Line \[gray\] labelled "10" drawn in plane (start=(3.6, 1.4), end=(6.6, 1.9)); edge\_cd — a Line \[gray\] labelled "2" drawn in plane (start=(6.6, 4.9), end=(6.6, 1.9)); edge\_ce — a Line \[gray\] labelled "6" drawn in plane (start=(6.6, 4.9), end=(9.0, 3.6)); edge\_de — a Line \[gray\] labelled "3" drawn in plane (start=(6.6, 1.9), end=(9.0, 3.6)); node\_s — a Point \[text\] labelled "S" drawn in plane (location=(1.1, 3.7)); node\_a — a Point \[text\] labelled "A" drawn in plane (location=(3.6, 6.2)); node\_b — a Point \[text\] labelled "B" drawn in plane (location=(3.6, 1.4)); node\_c — a Point \[text\] labelled "C" drawn in plane (location=(6.6, 4.9)); node\_d — a Point \[text\] labelled "D" drawn in plane (location=(6.6, 1.9)); node\_e — a Point \[text\] labelled "E" drawn in plane (location=(9.0, 3.6)); value\_s — a Point \[text\] labelled "0" drawn in plane (location=(1.1, 3.7), show\_marker=False); value\_a — a Point \[text\] labelled "3" drawn in plane (location=(3.6, 6.2), show\_marker=False); value\_b — a Point \[text\] labelled "2" drawn in plane (location=(3.6, 1.4), show\_marker=False); value\_c — a Point \[text\] labelled "10" drawn in plane (location=(6.6, 4.9), show\_marker=False); value\_d — a Point \[text\] labelled "12" drawn in plane (location=(6.6, 1.9), show\_marker=False); region\_sba — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (4.25, 6.45), (3.05, 6…, fill\_opacity=0.2); tree\_statement — a Math \[text\] that says "$upright("predecessors") arrow.r upright("shortest-path tree")$"; heading\_cost — a Heading that says "Heap Cost and the Route Tree"; region\_sbac — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (4.25, 0.9), (7.2, 4.35), (7.1, 5.5…, fill\_opacity=0.2); region\_sbacd — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.15, 1.2), (7.3, 5.35), (3.05, 6.…, fill\_opacity=0.2); value\_e — a Point \[text\] labelled "14" drawn in plane (location=(9.0, 3.6), show\_marker=False); region\_all — a Polygon \[blue\] drawn in plane (vertices=((0.45, 3.7), (3.05, 0.65), (7.0, 1.15), (9.6, 3.05), (9.55, 4.…, fill\_opacity=0.2)

Actions:
- [09:42.041](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=582.0407708333333): region\_sb is indicated — a transient flash.
- [09:43.875](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=583.8747708333333): tree\_statement (the "upright("shortest-path tree")" part) is emphasized.
- [09:52.423](https://academa.ai/lectures/dijkstras-algorithm-a-spreading-frontier?t=592.4233333333333): tree\_statement (the "upright("shortest-path tree")" part) is no longer emphasized.