max flow min cost c++ algorithm
Hello folks,nice to meet you!Can somebody suggest an algorithm for finding the max flow and the min cost between a source and a consumer in an acyclic graph with determined max flow on every edge an the cost for transporting threw the edge
Umm... I remember I studied a "math" class years ago saying that the maximal flow was equal to the minimal cut ( A "cut" is when you "draw a line separating" the source and the sink, and you sum up the flows of the edges that cross your "cutting line". Now a minimal cut just means the minimum among all cuts that you can do).
The professor was also stressing the fact that the max flow min cut problem is a partial case of the simplex algorithm, and that is in fact so. What I would do if I were you is I would teach myself how to convert the min cut/max flow problem to a simplex problem ("linear programming problem"). You can google simplex algorithm, you will get many sites that teach you! As for the conversion from one of the problems to the other - try not to google that: you can do it yourself if you understand well enough the simplex algorithm!
For the simplex algorithm the best place I found is the German+the English Wikipedia articles (honestly), and I actually DID program the simplex algorithm for my work about a year ago. All other sites I visited were rather a waste of time because they were trying to sound science-y way too much, instead of giving good information.
The professor was also stressing the fact that the max flow min cut problem is a partial case of the simplex algorithm, and that is in fact so. What I would do if I were you is I would teach myself how to convert the min cut/max flow problem to a simplex problem ("linear programming problem"). You can google simplex algorithm, you will get many sites that teach you! As for the conversion from one of the problems to the other - try not to google that: you can do it yourself if you understand well enough the simplex algorithm!
For the simplex algorithm the best place I found is the German+the English Wikipedia articles (honestly), and I actually DID program the simplex algorithm for my work about a year ago. All other sites I visited were rather a waste of time because they were trying to sound science-y way too much, instead of giving good information.
Last edited on
Just a starter on how to convert the flow restrictions to a simplex problem. Let Ai be the i-th node of your graph. Let Aij be the flow from the Ai-th node to the Aj-th node. Then the restrictions on the flow are:
1.
2.
Well, I guess this immediately gives you a simplex problem... You need to worry how to enumerate all the edges, and probably other things but those you can know only after getting your hands on the job :)
1.
\sum_j Aij-\sum_k Aki=0, Ai is neither a source nor a sink This means the sum of flows in the node equals the sum of flows out of the node. This equality must hold for all nodes but the source and the sink. 2.
Mij>= Aij>=0 This means the flow cannot be negative (*ugh*) and has an upper-bound-flow (that is given by the conditions of the problem, otherwise you will choose a single optimal path and transport as much as you can through it).Well, I guess this immediately gives you a simplex problem... You need to worry how to enumerate all the edges, and probably other things but those you can know only after getting your hands on the job :)
Last edited on
Topic archived. No new replies allowed.