Directed Graph
Edges have a direction; in-degree and out-degree differ.
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
Arrowheads on edges; a traversal only follows arrows forward.
Cost
| add edge | O(1) |
|---|---|
| out neighbours | O(out-deg) |
| Space | O(V + E) |
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, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Shortest Paths covers these too, in the same run.