Sunday, January 30, 2011

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 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

No comments:

Post a Comment