Other algorithms / interactive lesson
Solve the assignment problem step by step with the Hungarian algorithm. Watch row and column reductions, starred and primed zeros, cover changes, alternating paths, and the final minimum-cost matching.
About the algorithm
The Hungarian algorithm solves the assignment problem: match every row object to exactly one column object so that the total cost is minimum. It does this by transforming the matrix with row and column operations, then searching for a perfect matching among zeros.
Harold Kuhn published the Hungarian algorithm in 1955, naming it after earlier results by Hungarian mathematicians Dénes Kőnig and Jenő Egerváry. James Munkres later refined the method and proved a strongly polynomial running time, so the algorithm is also known as the Kuhn-Munkres algorithm.
First subtract row minima and column minima so that every row and column contains at least one zero. Then greedily star independent zeros to create a partial matching. If every column containing a star covers the whole matrix, the assignment is complete. Otherwise, search for uncovered zeros, prime them, and either shift covers or build an alternating path that flips stars and primes to enlarge the matching. When no uncovered zero exists, adjust the matrix by the smallest uncovered value and continue. The final starred zeros identify an optimal assignment.
The algorithm is used in workforce assignment, task scheduling, object tracking in computer vision, matching detections between frames, resource allocation, and many optimisation problems that can be modelled as minimum-cost bipartite matching.
Code companion
Connect each visual decision to an implementation pattern.
reduce every row by its minimum
reduce every column by its minimum
star independent zeros greedily
cover columns containing starred zeros
while not all columns are covered:
if there is an uncovered zero:
prime it
if there is no starred zero in the same row:
build alternating star/prime path
flip the path
clear covers and primes
cover columns containing starred zeros
else:
cover the row and uncover the starred zero's column
else:
m = smallest uncovered value
subtract m from every uncovered cell
add m to every doubly covered cell
return starred zeros as the optimal assignment