HekpoMaH's blog

Curious Question About Flow
By HekpoMaH, 11 years ago, In English

Hi. We all know algorithms that find maximal flow, but is there an algorithm that finds minimum flow? For example let's take the following task: Given N workers and N jobs. Each worker takes different amount of money for doing each job and each job can be done by only one worker. Assign the workers to the jobs, so as to the sum of money is minimum. P. S. Apart from using Hungarian algorithm, is there another way?

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

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Min Cost Max Flow

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

Change the cost ci of every edge to cmax - ci. Then, it becomes an algorithm for maximum flow.

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

In fact, minimal flow is 0, but it's not (I guess) what you're asking about.
What you really need is the min-cost flow algorithm, which is quite similar to Ford-Fulkerson algorithm: the difference is only that you search augmenting paths using not DFS, but any shortest-paths algorithm (like Ford-Bellman) that allows weights to be negative (in this case, weights are the costs of the edges).

→ Reply