CODEWITHSUNDEEP
javaalgorithmhungarian-algorithm
Ayrton Senna
Ayrton Senna

Reputation: 3835

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

Upvotes: 5

Views: 1815

Answers (1)

gaborsch
gaborsch

Reputation: 15758

An answer from a Hungarian: :)

  • Calculate the number of 0 elements for each row and column. (call it row[] and column[])
  • Select the minimum positive value of the rows and columns. For example let it be 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.
  • Select a 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])
  • Set column[3] to 0 (next time we shouldn't select). Also set row[1] to 0.
  • Iterate in all elements in column[3], if you find a 0 element, decrease the corresponding row[i] value by 1
  • If you don't find a positive value in neither row or column, you are finished.

Upvotes: 3

Related Questions