DAG Shortest Path
Relax each vertex's edges once, in topological order: one pass, negative weights allowed.
Shortest Paths: DAG in topological order, with a negative edge
Relax 1 to 2: 0 + 2 = 2 against 2's current infinity. Shorter, so 2 becomes 2 with 1 as its parent.
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
Before this
Taught by the same lesson
Shortest Paths covers these too, in the same run.