I am trying to implement the Hungarian algorithm in Java. I have an NxN cost matrix. I am following this guide step by step and have reached step 9 -
"Select a matching by choosing a set of zeros so that each row or column has only one selected."
I already have the matrix with the 0s. I was trying to figure this out and the only thing that was working for me was a brute force method.
I also thought of choosing the first 0 I encounter, remove that column & row and repeat; But this method does not work.
Is there any trick or method? Something that's not too complex? Any suggestion would appreciated.
Thanks
An answer from a Hungarian: :)
0
elements for each row and column. (call it row[]
and column[]
)column[3]
(if the minimum value is found in a row
, the same applies, only swap rows and columns) If you have more than one with the same value, select any.0
element in that column, mark it. If you have more than one, select any, that has a positive row
value. (Suppose it is row[1]
)column[3]
to 0 (next time we shouldn't select). Also set row[1]
to 0.column[3]
, if you find a 0
element, decrease the corresponding row[i]
value by 1