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.