Weighted Graph
Each edge carries a cost. The setting for shortest paths and spanning trees.
Shortest Paths: Dijkstra from 0
Relax 0 to 1: 0 + 4 = 4 against 1's current infinity. Shorter, so 1 becomes 4 with 0 as its parent.
Cost
- Add edge
- O(1)
- Edge weight
- O(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.