Dijkstra
Repeatedly settle the unsettled vertex with the smallest tentative distance and relax its edges.
Unsettled vertices with a known distance: 0 at 0. The smallest is 0, so settle it: 0 is final, because every other route into 0 would pass through something at least as far and edges never shorten a path.
What you will see
SELECT MINIMUM -> RELAX neighbours -> UPDATE distances; settled vertices lock; the priority queue is visible.
Cost
| Best | O((V + E) log V) |
|---|---|
| Average | O((V + E) log V) |
| Worst | O((V + E) log V) |
| Space | O(V) |
Binary heap; O(V^2) with an array; requires non-negative weights.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, tentative distance and parent; each step announces the relaxation and whether it improved a distance.
Reduced motion: Distance updates change the label with a crossfade instead of radiating from the edge.
Related
Taught by the same lesson
Shortest Paths covers these too, in the same run.