AlgoScope

Directed Graph

Edges have a direction. In-degree and out-degree differ.

Data structures, data structure, beginnerAlso called digraph
Vertex 0 is settled at distance 0.412153001234u
Vertex 0 is settled at distance 0.412153001234u

Shortest Paths: Dijkstra on directed edges

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.

How shortest paths works

Cost

Add edge
O(1)
Out neighbours
O(out-deg)
Space
O(V + E)

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

Shortest Paths covers these too, in the same run.