DAG Shortest Path
Relax each vertex's edges once, in topological order: one pass, negative weights allowed.
Decision · step 4 of 15Shortest 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.
What you will see
Vertices lined up in topological order; each one relaxes its outgoing edges exactly once.
Cost
| Best | O(V + E) |
|---|---|
| Average | O(V + E) |
| Worst | O(V + E) |
| Space | O(V) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, tentative distance and parent; each step announces the relaxation and whether it improved a distance.
Reduced motion: Distance updates change the label with a crossfade instead of radiating from the edge.
Before this
Taught by the same lesson
Shortest Paths covers these too, in the same run.