Bellman-Ford
Relax every edge V-1 times. A further improvement means a negative cycle.
Shortest Paths: Bellman-Ford from 0
Pass 1, edge 0 to 1: 0 + 4 = 4 against infinity. Shorter, so 1 becomes 4.
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.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Shortest Paths covers these too, in the same run.