The matrix is set up in the following form:
X/Y | 1 | 2 | 3 | 4 | 5 A | 4 5 5 4 6 B | 6 7 7 5 8 C | 6 5 2 5 4 D | 4 3 4 7 6 E | 9 7 7 6 10
The steps of the Hungarian algorithm are as follows:
-If the matrix isn't square, make it square by adding rows of 0's
-Reduce the matrix (note that this is NOT a Linear Algebra reduction)
-Pick a greedy matching on the 0's
-Find the optimal matching with the bipartite matching algorithm
-If the matching isn't optimal, find the minimal Cover (found X vertices + unfound Y vertices).
-Based on the cover, find the minimal uncovered entry (call it m). Subtract m from every uncovered entry and add m to every double-covered entry.
-Pick a new greedy matching on the 0's and repeat
Some Pseudo-Code:
function hungarianAlgorithm(SquareCostMatrix matrix) foreach row in matrix min = findMin(row) foreach element in row element <-- element - min end foreach end foreach foreach column in matrix min = findMin(col) if min > 0 foreach element in column element <-- element - min end foreach end if end foreach while matrix.getNumberMatches() < matrix.getX().size() pickMatching(matrix) augmentMatching(matrix) minCover <-- matrix.getMinCover() foreach element in minCover if matrix.x.contains(element) cover row at element end if else cover column at element end else end foreach min <-- findMinUncovered(matrix) foreach row in matrix foreach element in row if isCovered(element) == FALSE element <-- element - min end if else if isDoubleCovered(element) element <-- element + min end if end foreach end foreach end while end function function findMinUncovered(Matrix matrix) min <-- infinity foreach row in matrix foreach element in row if isCovered(element) == FALSE AND element < min min <-- element end foreach end foreach return min end foreach function pickMatching(Matrix matrix) foreach row in matrix foreach element in row, indexed i if element == 0 AND hasMatching(column[i]) == FALSE match(element) end if end foreach end foreach end function
Now, let's work through an example with the following cost matrix:
X/Y | 1 | 2 | 3 | 4 | 5 A | 4 5 5 4 6 B | 6 7 7 5 8 C | 6 5 2 5 4 D | 4 3 4 7 6 E | 9 7 7 6 10
Each row has the following minimums:
A- 4
B- 4
C- 2
D- 3
E- 6
After subtracting the row minimums from each row, the matrix reduces to:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0 1 1 0 2 B | 1 2 2 0 3 C | 4 3 0 3 2 D | 1 0 1 4 3 E | 3 1 1 0 4
The only non-zero column minimum is at column 5, where the min = 2. Reducing the matrix again, we get:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0 1 1 0 0 B | 1 2 2 0 1 C | 4 3 0 3 0 D | 1 0 1 4 1 E | 3 1 1 0 2
Picking a greedy matching (using a * to denote a matched edge) on the 0's, we get:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0* 1 1 0 0 B | 1 2 2 0* 1 C | 4 3 0* 3 0 D | 1 0* 1 4 1 E | 3 1 1 0 2
The bipartite matching algorithm produces the forest: E --- 4 -*- B, meaning the matching is maximal. So it is necessary to reduce the matrix yet again. The min cover for this matching is: {4, A, C, D}. The double-covered elements are A4, C4, and D4. The remaining elements in the A, C, and D rows are single covered, as are the remaining elements in column 4.
The minimum amongst the uncovered elements is 1, so subtract it from the uncovered elements and add it to the double-covered elements. The updated matrix is as follows, with the greedy matching the same as the last one:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0* 1 1 1 0 B | 0 1 1 0* 0 C | 4 3 0* 4 0 D | 1 0* 1 5 1 E | 2 0 0 0 1
Augmenting the matching leaves the final matrix:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0* 1 1 1 0 B | 0 1 1 0* 0 C | 4 3 0 4 0* D | 1 0* 1 5 1 E | 2 0 0* 0 1
Looking at the original cost matrix, that leaves the final cost at:
3 + 2 + 6 + 4 + 3 = 18