Dijkstra
Repeatedly settle the unsettled vertex with the smallest tentative distance and relax its edges.
Shortest Paths: Dijkstra from 0
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
- 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.
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Shortest Paths covers these too, in the same run.