Hungarian Algorithm Explained (Step-by-Step)
The Hungarian algorithm (also called the Kuhn–Munkres algorithm) is a polynomial-time method to solve the assignment problem: choose exactly one job per worker and one worker per job to minimize total cost.
If you want the “problem family” context first, see assignment vs transportation problem. For many solved matrices, see assignment problem examples.
- The assignment model and why Hungarian works
- Row/column reduction, covering zeros, and the adjustment step
- A dual (potentials) interpretation via primal–dual ideas
- Unbalanced assignment (dummy rows/cols) via unbalanced assignment
On this page
Quick takeaway: Hungarian algorithm repeatedly transforms the cost matrix without changing which assignments are optimal. It creates many zeros (tight reduced costs), then finds a set of independent zeros (one per row/column). If there are not enough independent zeros, it performs a structured adjustment step and repeats.
Assignment problem model (matrix + constraints)
Given an n×n cost matrix C = [c(i,j)], choose exactly one entry in each row and each column to minimize total cost.
Binary variable form
minimize Σ_i Σ_j c(i,j) x(i,j)
subject to Σ_j x(i,j) = 1 for each i
Σ_i x(i,j) = 1 for each j
x(i,j) ∈ {0,1}
This is closely related to linear programming. The assignment structure is also tied to the graph view: bipartite matching & assignment.
Core idea: reduced costs, dual potentials, and zeros
A lecture-level way to understand Hungarian is through the LP dual (often called potentials):
choose row potentials u_i and column potentials v_j so that:
u_i + v_j ≤ c(i,j) for all i,j
The quantity c(i,j) - u_i - v_j is a reduced cost (nonnegative).
Cells where c(i,j) - u_i - v_j = 0 are “tight” and become zeros in the reduced matrix.
Hungarian algorithm manipulates the matrix exactly by updating these potentials—creating zeros and searching for a perfect matching among them.
If you want the general duality story, see primal–dual relationship in LP.
Hungarian algorithm steps (full)
- Row reduction: subtract each row minimum from that row.
- Column reduction: subtract each column minimum from that column.
- Find a maximum set of independent zeros (a matching among zeros).
- Cover all zeros with a minimum number of lines (rows/columns).
-
If the number of lines equals
n, you can form an optimal assignment from independent zeros. Otherwise:- let
k= smallest uncovered value, - subtract
kfrom all uncovered entries, - add
kto all entries at intersections of two lines, - repeat from step 3.
- let
Worked examples
Worked example
Example 1 (4×4, minimization): includes “cover zeros → adjust” loop
Cost matrix (minimize):
J1 J2 J3 J4 W1 90 75 75 80 W2 35 85 55 65 W3 125 95 90 105 W4 45 110 95 115
Step 1 — Row reduction
Subtract each row minimum:
- Row W1 min=75 → (15, 0, 0, 5)
- Row W2 min=35 → (0, 50, 20, 30)
- Row W3 min=90 → (35, 5, 0, 15)
- Row W4 min=45 → (0, 65, 50, 70)
J1 J2 J3 J4 W1 15 0 0 5 W2 0 50 20 30 W3 35 5 0 15 W4 0 65 50 70
Step 2 — Column reduction
Compute column minima and subtract:
- Col J1 min=0 (no change)
- Col J2 min=0 (no change)
- Col J3 min=0 (no change)
- Col J4 min=5 → subtract 5 from column J4
J1 J2 J3 J4 W1 15 0 0 0 W2 0 50 20 25 W3 35 5 0 10 W4 0 65 50 65
Step 3 — Try selecting independent zeros (one per row/col)
Identify zero positions:
- W1 has zeros at J2, J3, J4
- W2 has zero at J1
- W3 has zero at J3
- W4 has zero at J1
Notice a conflict: both W2 and W4 only have a zero in column J1, so you cannot assign both using only zeros yet. This is exactly when you need the line-cover + adjustment step.
Step 4 — Cover all zeros with minimum number of lines
A minimal cover (one valid option) is:
- Cover column J1 (covers zeros of W2 and W4)
- Cover column J3 (covers zero of W3 and one of W1’s zeros)
- Cover row W1 (covers remaining zeros in that row)
That uses 3 lines (less than 4), so we must adjust.
Step 5 — Adjustment step
Find the smallest uncovered value (not covered by any line). Under the cover above:
- Uncovered candidates include W3J2=5, W2J4=25, W4J2=65, W4J4=65, etc.
- Smallest uncovered value is k = 5.
Now apply the rule:
- Subtract 5 from every uncovered element
- Add 5 to every element covered twice (intersections of a covered row and covered column)
- Leave singly covered elements unchanged
Resulting matrix (after the adjustment) becomes:
J1 J2 J3 J4 W1 15 0 0 0 W2 0 45 15 20 W3 35 0 0 5 W4 0 60 50 60
Step 6 — Now pick independent zeros
We can now choose a consistent set, for example:
- W2 → J1 (zero)
- W3 → J2 (zero) or J3 (zero) — pick J2
- W1 → J4 (zero) (or J3/J2)
- W4 cannot use J1 now because taken; but we still need to check if another adjustment is needed or choose a different combination.
If you choose:
- W4 → J1 (zero)
- W2 → J4 (20) would not be zero, so not allowed if we require all-zero selection at this stage
This matrix is closer but may still need another iteration (depending on the matching procedure). The key learning is: the adjustment step creates new zeros in uncovered positions while maintaining optimality equivalence.
Worked example
Example 2 (3×3): quick case where independent zeros exist immediately
Cost matrix:
J1 J2 J3 W1 9 2 7 W2 6 4 3 W3 5 8 1
This is a good “first practice” matrix; after reductions you can often select independent zeros directly. Compare with a more iterative example above.
Worked example
Example 3 (maximization): convert profit to cost then solve
For maximization (profit) assignment, convert profit to an equivalent minimization cost matrix, e.g.:
cost(i,j) = Pmax - profit(i,j), then apply Hungarian normally.
Worked example
Example 4 (unbalanced): add dummy row/column
If jobs ≠ workers, add dummy row/column and solve the square matrix. Full details: unbalanced assignment problem.
Unbalanced assignment using dummy rows/columns
When the matrix is rectangular (e.g., 3 workers and 4 jobs), convert it to square by adding a dummy worker or dummy job. The dummy represents “unused worker” or “unfilled job,” depending on which side is short.
Full guide with examples: Unbalanced assignment (dummy rows/cols).
Common variants (maximization, forbidden pairs)
Maximization
How to solve maximum profit assignment
Convert to minimization using a constant shift. This preserves the identity of optimal assignments because adding/subtracting the same constant per row/column doesn’t change the argmin structure.
Forbidden pairs
What if some worker-job assignments are not allowed?
A common modeling tactic is to assign a very large penalty cost to forbidden cells so they are never chosen. If the “forbidden” structure is important, consider modeling as an ILP and solving with an ILP/MILP solver: integer linear programming.
Avoid absurdly huge penalties (numerical issues). For solver numerics concepts, see integrality tolerance.
Questions people ask
Questions people ask
Why do row and column reductions not change the optimal assignment?
Subtracting a constant from every element of a row subtracts the same constant from the total cost of every assignment (since every feasible assignment uses exactly one cell from that row). The argmin stays the same.
Questions people ask
What does “cover all zeros with minimum number of lines” mean?
You draw the fewest horizontal/vertical lines so every zero is crossed by at least one line.
If that minimum number equals n, there exists a full set of independent zeros (an optimal assignment can be built).
Questions people ask
Why does the adjustment step work?
Subtracting the smallest uncovered value creates new zeros (new tight reduced costs) without violating nonnegativity of reduced costs. From a dual viewpoint, it updates row/column potentials while keeping feasibility.
Questions people ask
Is Hungarian algorithm the same as Kuhn–Munkres?
In most OR references, “Hungarian” and “Kuhn–Munkres” refer to the same core approach for the linear assignment problem.
Questions people ask
Can Hungarian solve a rectangular (unbalanced) matrix directly?
Standard Hungarian is described for square matrices. For rectangular cases, add dummy rows/columns to make it square: unbalanced assignment.
Questions people ask
What is the time complexity of the Hungarian algorithm?
It is commonly given as O(n³) for an n×n assignment matrix (depending on implementation details).
Questions people ask
Can there be multiple optimal assignments?
Yes. If there are alternative independent-zero selections leading to the same cost, you have multiple optima. Related concept: multiple optimal solutions.
Questions people ask
When should I use transportation methods instead of Hungarian?
If you have general supplies and demands (not strictly one-to-one), your model is closer to transportation. See assignment vs transportation problem.
Questions people ask
How do I implement Hungarian algorithm in Python?
Use SciPy’s assignment solver: Hungarian algorithm in Python (SciPy).
What to do next
- Practice more matrices: assignment problem examples.
- Unbalanced/dummy modeling: unbalanced assignment.
- Graph interpretation: bipartite matching & assignment.
- Python implementation: Hungarian algorithm in Python.
Disclaimer
This guide is for educational and informational purposes. Real assignment/scheduling problems may include constraints not captured by the one-to-one assignment model (skills, shifts, precedence, fairness, overtime, multi-period requirements). In such cases, you may need a broader optimization model (often ILP/MILP) rather than Hungarian alone. Always validate assumptions and results using appropriate domain constraints and, when necessary, a production-grade solver. Read the full disclaimer.
Related guides
Sources
- Kuhn (1955) — The Hungarian method for the assignment problem (Naval Research Logistics Quarterly)
- Munkres (1957) — Algorithms for the Assignment and Transportation Problems (SIAM)
- Burkard, Dell’Amico, Martello — Assignment Problems (SIAM book page)
- Wikipedia — Hungarian algorithm (overview)
- Wikipedia — Assignment problem (overview)