## MinCost MaxFlow code

**Moderator:** Board moderators

### MinCost MaxFlow code

hi, in the past days i have read somewhat about the mincost maxflow algorithm, and i have realized this seems to be an "obscure" topic, because although there is information about the algorithms, little is covered about an actual implementation in a language like c++, this has been what i have learned

- You can solve it, by finding a maxflow, and then runnning succesive Bellman Ford to reduce the cost, in this case what seems difficult to me is finding the actual negative cycle, and i don't know if this is a efficient way to solve the problem.

- In the site of Igor Naverniouk, (http://shygypsy.com/tools/mcmf3.cpp), there is indeed a code to solve this problem, but it uses some algorithm that i don't understand, and as i see it uses some kind of Dijkstra, but as far as i know Djikstra can't be used for finding shortest path with negative weights, so i'm every time more confused.

So i'm asking for help, if you know any good resource with a good implementation, or can explain how the code above works, it would be very helpful, thanks in advance

- You can solve it, by finding a maxflow, and then runnning succesive Bellman Ford to reduce the cost, in this case what seems difficult to me is finding the actual negative cycle, and i don't know if this is a efficient way to solve the problem.

- In the site of Igor Naverniouk, (http://shygypsy.com/tools/mcmf3.cpp), there is indeed a code to solve this problem, but it uses some algorithm that i don't understand, and as i see it uses some kind of Dijkstra, but as far as i know Djikstra can't be used for finding shortest path with negative weights, so i'm every time more confused.

So i'm asking for help, if you know any good resource with a good implementation, or can explain how the code above works, it would be very helpful, thanks in advance

(2) I haven't seen Igor's code yet, but I'm suspecting he is using the Cheapest Augmenting Path algorithm. The basic idea is to weight each node with a "potential", and for each edge (u,v), calculate a reduced cost

c'(u,v) = c(u,v) + p(u) - p(v)

where c(u,v) is the original cost of the edge and p(u) and p(v) are the potentials of the node.

If there are no negative cycles in the graph, then if for each node, we use the shortest distance from the source as the potential p, then all reduced costs are non-negative by the triangle inequality. Then Dijkstra can be used to find an augmenting path of minimal reduced cost from source to sink (which is also the minimal un-reduced cost path).

Note that you don't need all edge weights to be non-negative, just have no negative weight cycles. You can use an initial Bellman-Ford to calculate the initial potentials this way.

With each augmenting path found, the potentials can be updated by

p'(u) = p(u) + d(s,u)

where d(s,u) is the shortest path distance to u from source s using the current reduced costs. It can be proven that all reduced costs remain non-negative. Then Dijkstra can be used again and again until no augmenting path can be found, in which case you have a max-cost min-flow.

Interestingly enough, this algorithm gives the minimum-cost flow for every possible (non-negative) flow value from source to sink.

(1) why the potential assigned to each vertex grantes us that there is no negative path?

(2) i dont understand how can i modify this algorithm to allow negative costs, could you explain a little more

(3) what about the maxcost-maxflow problem, how can this algorithm be modified to give us the flow with maxcost?

thanks in advance

d(s,v) <= d(s,u) + c(u,v) --- (1)

for all u,v where s is the starting vertex, d(s,u) and d(s,v) minimum distances to vertices u and v and c(u,v) the cost of the edge between u and v.

Rearranging gives c(u,v) + d(s,u) - d(s,v) >= 0 and therefore setting the initial potential of a vertex to be the minimum distance from s to it will always result in initial non-negative reduced costs.

To prove that the reduced costs always remain non-negative, use induction. I'll give a brief outline of the proof - the details can be found online:

After augmentation, we have p'(u) = p(u) + d'(s,u) where p is the original potential, p' the new potential, and d'(s,u) the distance from s to u under potential p (the original potential).

For any edge (u,v), the new reduced cost is now changed by d'(s,u) - d'(s,v). If an edge in the new residual network was previously in the old residual network, we can again appeal to the triangle inequality (1) above.

If an edge (u,v) in the new residual network was not in the old residual network, then (v,u) must be on some shortest path from s to t. Then the reduced cost on (u,v) must then be equal to 0, because d'(s,v) = d'(s,u) + c'(u,v) where c'(u,v) is the old reduced cost on (u,v) and the new reduced cost is c'(u,v) + d'(s,u) - d'(s,v) = 0.

(2) Again, if there are no negative cycles (but negative costs), we can assign initial potentials by shortest path distances from the source node. The shortest path distances can be found by Bellman-Ford.

(3) Negate all costs. Again, after negation we need to avoid negative-cost cycles.

actually i'm using Igor's code for mincost max flow, and for max cost I let cost

*[j] = MaxCost we got-cost*

*[j] and rerun the mincost maxflow.*

I tried to multiply each float number of the input by 100 and work with integers only and divide at the end but also got WA.

Can anyone give a hint to a special case or a probable mistake?

ThanksI tried to multiply each float number of the input by 100 and work with integers only and divide at the end but also got WA.

Can anyone give a hint to a special case or a probable mistake?

Thanks

### world finals,2006 Problem B

hello ,

igor once told me that his min cost max flow code given in his site doesnt work for the problem u mentioned . this is the problem of the world finals , 2006 problem B . so u may check with igor in this matter . may be he can help . or u can write a min cost max flow code on ur own .

happy coding

bye bye

igor once told me that his min cost max flow code given in his site doesnt work for the problem u mentioned . this is the problem of the world finals , 2006 problem B . so u may check with igor in this matter . may be he can help . or u can write a min cost max flow code on ur own .

happy coding

bye bye

In good company

### network flow pdf

here's couple:Kallol wrote:can anyone provide me with some links or soft book/tutorial/pdf for network flow algorithm and its variations??

http://ww3.algorithmdesign.net/handouts/MaxFlow.pdf

http://web.mit.edu/15.053/www/AMP-Appendix-C.pdf

http://activities.tjhsst.edu/sct/lectures/netflow.pdf

Follow this link, you'll get everything.

http://www.topcoder.com/tc?module=Stati ... d2=maxFlow

http://www.topcoder.com/tc?module=Stati ... d2=maxFlow