Directed Graph
Edges have a direction. In-degree and out-degree differ.
Shortest Paths: Dijkstra on directed 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.
Cost
- Add edge
- O(1)
- Out neighbours
- O(out-deg)
- Space
- O(V + E)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Shortest Paths covers these too, in the same run.