AlgoScope

Dijkstra

Repeatedly settle the unsettled vertex with the smallest tentative distance and relax its edges.

Shortest path, algorithm, intermediate
Vertex 0 is settled at distance 0.412153001234u
Vertex 0 is settled at distance 0.412153001234u

Shortest Paths: Dijkstra from 0

Decision, step 2 of 13

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.

Leads to

Topics that need this one first.

Taught by the same lesson

Shortest Paths covers these too, in the same run.