javaalgorithmhungarian-algorithm

Hungarian algorithm - Last step of selecting 0s from such that each row and column has only one selected


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


Solution

  • An answer from a Hungarian: :)