Successive shortest paths algorithm description with source

•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