kingofnumbers's blog

minimum cost maximum flow
By kingofnumbers, 12 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?
»
12 years ago, # |
  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
»
12 years ago, # |
← 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
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    sorry I cant read russian.

    Thank you anyway.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use google chrome

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        first, google chrome is a browser not a translator.

        second, if you mean that I should use translate.google.com , I believe that google don't translate texts well.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          U're very right! Read an article translated by something like google translate or promt is a kind of bullshit. Though, I have no idea цhere to search for that kind of articles, I probably know who it makes sense to try to ask directly. ilyaraz might show u the wondered article. If he does this, plz post it there or send me a message, cause for some reason i want to take a look on it too.

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you post the article which helped you to learn(hope u learnt it by this time)

          → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can never solve mininum cost flow by dijkstra. If original weight of an arc is positive, then in the residual network the reverse arc has negative weight. And dijkstra can't handle it.

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

Among TopCoder tutorials, Minimum Cost Flow section.

→ Reply