Find the maximum flow f, in which f(e) is the maximum flow possible in a given edge e

Question

Given a flow network, G(V,E), a source s, a sink t and a capacity function c: E --> R U {0}. Also, given an edge e=(u,v) in E. I need to find an efficient algorithm to find among all the maximum flows from s to t, a maximum flow f in the network, in which f(e) is the maximum flow possible in the edge e.

Please solve the problem and explain why the algorithm works correctly.

Answer 1

If I understood your problem correctly you need Ford-Fulkerson algorithm to solve standard maximum flow problem. Basically it works like this:

1. Assign 0 flow to every edge.

2. Build a residual network (of useful edges).

3. Find any path satisfying your requirements.

4. Update network. Is there any way that you can have more flow? If not, stop, else go to point 2.