Bellman-Ford
Relax every edge V-1 times; a further improvement means a negative cycle.
Pass 1, edge 0 to 1: 0 + 4 = 4 against infinity. Shorter, so 1 becomes 4.
What you will see
Whole-graph relaxation passes; distances settle pass by pass; a V-th pass that changes anything flags a negative cycle.
Cost
| Best | O(E) |
|---|---|
| Average | O(V * E) |
| Worst | O(V * E) |
| Space | O(V) |
Best case with early exit when a pass changes nothing.
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
Related
Taught by the same lesson
Shortest Paths covers these too, in the same run.