Блог пользователя HekpoMaH

Curious Question About Flow
Автор HekpoMaH, 11 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Min Cost Max Flow

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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).

→ Ответить