The Hungarian Algorithm is used to find the minimum cost in assignment problems that involve assigning people to activities. The following videos explain how the Hungarian algorithm works in QCE General Maths. The steps for solving Hungarian algorithms are as follows:
- Subtract row minima (for each row, find the lowest element and subtract it from each element in that row)
- Subtract column minima (for each column, find the lowest element and subtract it from each element in that column)
- Cover all zeroes with minimum number lines (Cover all zeros in the resulting matrix using a minimum number of horizontal and vertical lines. If n lines are required, an optimal assignment exists among the zeros. The algorithm stops. If less than n lines are required, continue with Step 4.)
- Create additional zeros (Find the smallest element (call it k) that is not covered by a line in Step 3. Subtract k from all uncovered elements, and add k to all elements that are covered twice.)
What is the Hungarian Algorithm
Watch these videos below to understand how the Hungarian Algorithm works. Most of these videos go over the same concept just explained slightly differently.
Want to learn more? Check out more of our QCE General Maths resources here!