VISUALISERS · FOUNDATIONS

Dijkstra visualiser

Dijkstra answers why the cheapest node next, every time?

Every node in the figure is in one of three states: settled — its distance is final, and the badge on it says which turn it settled on; frontier — reached, with a distance that can still fall; not reached — no route to it yet, so its distance is still ∞.

Fit the whole diagram on screen Show it at full size, and pan

Speed

SETTLED

NODES

Nothing settled yet. Only the source has a distance.

“Step” advances one step, which is either settling the cheapest node on the frontier or relaxing one edge out of the node just settled; “Back” retraces one. “Run” plays out the steps that are left. Once all seven nodes are settled the run is over — “Step” and “Run” then have nothing left to do, and “Reset” returns to the start.

Dijkstra settles the cheapest node on the frontier every time, so the settle order never goes backwards in distance. Settling is final — a settled node is never looked at again — and that is why one negative edge breaks the answer: a cheaper route into an already-settled node would arrive too late to be taken.

Want an explanation to go with the picture? Find a guided starting point →