P_Nyagolov's blog

Implementing Hungarian Algorithm
By P_Nyagolov, 10 years ago, In English

Hello everybody,

A while ago I decided to learn about Hungarian algorithm. After watching some videos and reading some articles I think I got the main idea:

1) Find the minimum number in each row and subtract it from all elements in the row.

2) Find the minimum number in each column and subtract it from all elements in the column.

3) Cover all zeroes with minimum number of vertical and/or horizontal lines.

4) If the number of the lines is N, then we have found our assignment. Otherwise, find the minimum uncovered number, subtract it from all uncovered numbers and then go back to step 3.

Well, the thing is that I never found a good implementation. I can implement step 1 and 2. For step 3, I think that we can check whether the minimum number of lines is equal to N using bipartite matching. But if the minimum number is less than N, I don't know how I can find those covering lines. Please, help me with implementing it.

Thanks in advance!

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

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The best implementation I had ever seen is in topcoder turorials.

There is a O(N^4) and a O(N^3) clean implementation.

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

Go to line 1396 here to see my O(n^3) implementation in a single method.

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

The best implementation I know is that of Andrey Lopatin. It is surprisingly short and works with negative weights. You can find it on e-maxx: http://e-maxx.ru/algo/assignment_hungary#6

There is an English translation here: http://zafar.cc/2017/7/19/hungarian-algorithm/

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think this article is useful but it says nothing about proof of correctness of O(n^4) algorithm. I mean it doesn't explain why adding vertices in this order leads to the optimal answer.

    Intuitively I see that algorithm adds in each step an edge with max cost which may create an augmenting path but I don't understand why it can decrease its cost? Can you give me please any test case on which first version of Hungarian algorithm will decrease u[i]+v[j]?

    UPD: Now I got it.

    → Reply