Flagship - composed lesson

Dijkstra, one cursor at a time

A scroll lesson, an embedded player, an intro tour and a glossary - all on one page, all the same primitive. Scroll and the paused player follows; play and it runs the whole search.

01The grid

Eight columns, five rows. S is the start, G the goal. Walls block movement; rough ground (the shaded cells) costs 4 to enter and open ground costs 1. Those costs are the edge weights.

The question is not "how many moves" but "what is the cheapest route" - a detour around rough ground can beat a straight line through it.

02The frontier

Dijkstra keeps a frontier: cells it has reached but not finished with, each carrying a tentative distance. It starts with just S at distance 0.

Every round pops the cheapest frontier cell from a priority queue. On the grid, dashed outlines are the frontier and the number in a cell is its current best distance.

03Relaxation

The popped cell makes offers to its neighbours, then becomes final. Two halves:

04Offers

For each neighbour, dist[u] + w is an offer. If it beats what the neighbour already has, it wins: that is relaxation. Highlighted cells on the grid were relaxed this frame.

On this grid the weight lives on the cell you enter, so the first offer a cell receives is already its best. On a general graph with weights on edges, a later offer can undercut an earlier one - the algorithm doesn't care either way.

05Settling

The cell popped from the queue is settled - its distance will never change again. Settled cells turn green and the explored region grows outward like a ripple, cheapest first.

The ripple bends: it flows quickly over open ground and slowly over rough ground, so the frontier is not a circle but a contour of equal cost.

06The path

When G is settled the search stops. Every settled cell recorded who made its winning offer, and those back-pointers form a shortest-path tree. Walking it from G to S gives the route.

Press play to watch the whole search, or scroll back up: each chapter seeks the paused player to its own frame.

Glossary

Collected from the provider's entries - no list passed by hand.

Edge weight

The cost of one move. Here it is the cost of entering a cell: open ground costs 1, rough ground 4. Dijkstra requires weights to be non-negative - that is what makes settling safe.

Tentative distance

The best cost found so far to reach a cell. It only ever decreases, through relaxation, and becomes final once the cell is settled.

Frontier

Cells that have a tentative distance but are not settled yet - the boundary between explored and unexplored. Kept in a priority queue.

Priority queue

A collection that hands back its smallest element first. Dijkstra pops the frontier cell with the lowest tentative distance. This demo scans an array; a binary heap makes each pop logarithmic.

Relaxation

Offering a neighbour a path through the current cell: if dist[u] + w beats the neighbour's tentative distance, the offer replaces it and the neighbour joins the frontier.

Settled

A cell whose distance is final. Because every weight is non-negative, no later path can undercut the cheapest frontier cell - so popping it settles it.

Shortest-path tree

Each settled cell remembers the neighbour that made its winning offer. Following those back-pointers from any cell walks the cheapest route home to the start.