P_Nyagolov's blog

By P_Nyagolov, 6 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

»
6 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Peace be upon you.

A nice implementation is found in the dlib library here :

http://dlib.net/optimization.html

Search for "max_cost_assignment". There's an example project you can build and run with the name "max_cost_assignment_ex"

»
5 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.

»
7 weeks 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/