Page 1 of 2
MinCost MaxFlow code
Posted: Thu Aug 24, 2006 8:40 pm
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
Posted: Fri Aug 25, 2006 3:43 am
(1) Finding the negative cycle is a very short extension of Bellman-Ford. This isn't really efficient, though.
(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.
Posted: Wed Aug 30, 2006 1:57 am
ok, thanks for replying, i think i have understood now, and i think i have implemented right, i just have some doubts, maybe you can answer me:
(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
Posted: Wed Aug 30, 2006 6:21 pm
(1) Assuming no negative cycle, the following inequality ALWAYS holds:
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.
Posted: Wed Sep 06, 2006 7:02 pm
Thanks for your help, now i think i understand the problem well, and solved several problems too
, thanks again
Posted: Fri Oct 20, 2006 3:02 pm
I'm trying to solve this problem http://acmicpc-live-archive.uva.es/nuev ... php?p=3562
which is very much related to this thread but always get WA
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?
world finals,2006 Problem B
Posted: Fri Oct 20, 2006 7:47 pm
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 .
Posted: Sat Oct 21, 2006 1:36 am
The code works on that problem. Frank Chu (the co-author of the code) has just got it accepted. You must have a bug in the way you are using it.
Posted: Sat Oct 21, 2006 5:28 am
thanx igor for ur concern . now iLL try to get the problem accepted . thanx for all the codes in ur site . it is a nice learning curve for newcomer like us .
Posted: Sun Jul 29, 2007 5:51 am
can anyone provide me with some links or soft book/tutorial/pdf for network flow algorithm and its variations??
network flow pdf
Posted: Mon Jul 30, 2007 7:23 am
Posted: Mon Jul 30, 2007 5:09 pm
Thnak you ...great help
Now can you give me similar links for hangariun methods for solving bipartite matching problem??
Posted: Mon Jul 30, 2007 6:48 pm
Posted: Mon Jul 30, 2007 10:07 pm
What is the best complexity for bipertite matching problem ?? I can code a dfs like code with complexity O(m*n*n). Is there any better algo??
Posted: Sun Nov 25, 2007 9:58 pm
Abednego's code for mincostmaxflow contains FIXMEs.
I got AC 10806 and 10594 with it.
How that code must be modified in order for it to handle multiple edges with different costs?