Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

kingofnumbers's blog

minimum cost maximum flow
By kingofnumbers, 13 years ago, In English

hi

I have searched the internet alot but didnt find a good article about min cost max flow

given a directed graph each edge has cost for transfering one unit and capacity that spicify maximum number of units can pass the edge find minmum total cost to transfer K units from node S to node T(not neccessery max flow only K units)

can you give me good article to solve this problem

thanks

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

You can add another node S1, and conected to node S with capacity K and cost 0, so the answer to the problem is the same but taking as source the node S1 and sink the node T.

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it -6 Vote: I do not like it

http://e-maxx.ru/algo/min_cost_flow — If you know russian you can try this.
The algorithm is very similar to the Edmonds-Karp algorithm. (Wiki)
In the Edmonds-Karp algo you find an augmenting path using BFS because it finds the shortest path (min amounts of edges) from the source to the sink. If you want to solve the min cost flow problem you should use an algo which finds the shortest path in a weighted graph (weight of an edge is the cost of transfering one unit of flow), e.g. Dijkstra.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Among TopCoder tutorials, Minimum Cost Flow section.

→ Reply