•Start with flow f with f(u,v)=0 for all u,v.
•repeat until value(f ) = r
–Find the shortest path P in Gf from s to t
–Let q be the minimum residual capacity of an edge on P.
–Send min(q,r – value(f)) additional units of flow across P.
On the successive shortest paths algorithm :
•May use exponential running time
•Assume G has no negative edge costs.
•Gives optimal answer.
–Invariant: f has minimum cost among all flows with value value(f).
•Suppose we obtain f’ from f by sending across P.
•Let f’’ be a minimum cost flow with same value as f’.
•Write f’’ – f as weighted sum of paths from s to t in Gf and circuits in Gf. Argue that cost(f’ – f) / cost(f’’ – f), using that:
–P is shortest path
–Circuits have non-negative costs, by optimality of f.
Source code link is given here