Framework
SPFA (Bellman-Ford variant) to find shortest (in cost) augmenting path. Augment. Repeat until no s-t path.
Advertisement
Why shortest path
Follows from potential function argument. Shortest-augmenting-path preserves optimality invariant.
Advertisement
Complexity
O(F × E × V) with SPFA where F = max flow value. Pseudo-polynomial in flow value.
Johnson-like reweighting
Use potentials from previous SPFA as node prices. Enables Dijkstra on subsequent iterations (all reduced costs ≥ 0).