Hungarian Algorithm Explained (Step-by-Step)

Given an n×n cost matrix C = [c(i,j)], choose exactly one entry in each row and each column to minimize total cost. This is the classic linear assignment problem.

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.

How does the assignment problem compare to related problems?

A quick comparison helps clarify when Hungarian algorithm applies versus other classic OR methods:

See also: assignment vs transportation problem and bipartite matching & assignment.

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.

Why “Hungarian”? Harold Kuhn named the method in honor of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry, whose earlier theorems on bipartite graphs (König’s theorem) are the theoretical foundation for why the algorithm’s zero-cover step correctly identifies an optimal assignment.

1. Row reduction: subtract each row minimum from that row.
2. Column reduction: subtract each column minimum from that column.
3. Select independent zeros: try to pick zeros so that no two chosen zeros share a row or a column. (That selection corresponds to a valid one-to-one assignment.)
4. Cover all zeros with a minimum number of lines (rows/columns).
5. If the number of lines equals n, you can form an optimal assignment from independent zeros. Otherwise:
   • let k = smallest uncovered value,
   • subtract k from all uncovered entries,
   • add k to all entries at intersections of two lines,
   • repeat from step 3.

The star/prime method: finding independent zeros systematically

Step 3 above (“select independent zeros”) is easy to eyeball on a 3×3 matrix but becomes error-prone by hand once you reach 5×5 or larger. The star/prime method (the bookkeeping scheme inside the classical Munkres algorithm) gives you a deterministic procedure that never requires guessing.

Definitions

• Starred zero: a zero that is provisionally part of the assignment. No two starred zeros ever share a row or column.
• Primed zero: a zero that has been “flagged” while searching for a way to extend the current set of stars. Primes are temporary working marks, not part of the final assignment.
• Covered row/column: a row or column temporarily excluded from the search for uncovered zeros, using the line-cover idea from Step 4.
• Augmenting path: an alternating chain of primed and starred zeros that, when “flipped” (primes become stars, stars become unstarred), increases the number of independent zeros by exactly one.

The full procedure

1. Initial starring: scan the matrix; star a zero if its row and column contain no other starred zero yet.
2. Cover columns that contain a starred zero. If all n columns are covered, the starred zeros ARE the optimal assignment — stop here.
3. Search for an uncovered zero.
   • If none exists, go to Step 4 (numeric adjustment) using the current covers, then return to Step 2.
   • If found, prime it.
     • If its row already has a starred zero: cover that row, uncover that star’s column, and keep searching for uncovered zeros (repeat Step 3).
     • If its row has no starred zero: this primed zero is the start of an augmenting path — go to Step 5.
4. Numeric adjustment (only reached if Step 3 found no uncovered zero): let k = the smallest value among all uncovered cells. Subtract k from every uncovered cell; add k to every cell covered twice (at a covered-row/covered-column intersection); leave singly-covered cells unchanged. This creates at least one new uncovered zero. Return to Step 2.
5. Build and apply the augmenting path: starting from the primed zero Z0 found in Step 3, alternate:
   • find the starred zero in Z0‘s column (if any) → call it Z1,
   • find the primed zero in Z1‘s row → call it Z2,
   • repeat until you reach a primed zero whose column has no starred zero.
   Then unstar every starred zero in this chain and star every primed zero in it. Erase all remaining primes, remove all line covers, and return to Step 2 (you now have one more starred zero than before).

      J1  J2  J3
W1     0   0   4
W2     0   3   5
W3     0   6   0

Pseudocode

Level 1 — high-level overview

for each row:    subtract the row minimum
for each column: subtract the column minimum

repeat:
    find a maximum matching using only zero-cost cells
    if matching size == n:
        return matching          // optimal assignment found

    find the minimum number of lines covering all zeros
    k = smallest value not covered by any line
    subtract k from every uncovered cell
    add k to every cell covered by two lines
    // singly covered cells stay unchanged

Level 2 — star/prime bookkeeping (what “find a maximum matching” actually does)

function hungarian(cost):
    n = size of cost matrix
    subtract row minima, then column minima     // as above
    stars = empty n×n boolean grid
    primes = empty n×n boolean grid
    row_covered, col_covered = all false

    # initial starring
    for each zero cell (i, j):
        if no star in row i and no star in column j:
            star(i, j)

    loop:
        col_covered[j] = true for every column j containing a star
        if count(col_covered) == n:
            return read_assignment(stars)

        (i, j) = find an uncovered zero cell        // not in a covered row or column
        if no such cell exists:
            k = min value among all uncovered cells
            add k to cells covered by both a row and a column line
            subtract k from cells covered by neither
            continue loop                            // a new uncovered zero now exists

        prime(i, j)
        if row i already contains a starred zero at column j2:
            row_covered[i] = true
            col_covered[j2] = false
            continue loop                            // keep searching for uncovered zeros
        else:
            path = build_augmenting_path(i, j)
            for (r, c) in path: toggle_star(r, c)     // stars↔primes flip along the path
            clear all primes
            row_covered, col_covered = all false
            continue loop                            // re-cover columns, one more star exists now

function build_augmenting_path(start_i, start_j):
    path = [(start_i, start_j)]          // Z0: primed
    col = start_j
    loop:
        row = row_of_starred_zero_in_column(col)
        if row is None:
            return path                   // path ends on a primed zero
        path.append((row, col))          // Z1, Z3, ... : starred
        col = column_of_primed_zero_in_row(row)
        path.append((row, col))          // Z2, Z4, ... : primed

Why this matters for performance: a naive re-scan of the whole matrix for the smallest uncovered value at every adjustment step costs O(n²) per adjustment and can require up to O(n) adjustments, giving O(n³) in a straightforward implementation — or worse if the “find a maximum matching” step is also recomputed from scratch. Efficient implementations (including SciPy’s linear_sum_assignment) avoid repeated full re-scans by maintaining a running slack array (the smallest reduced cost currently reachable in each uncovered column), updating it incrementally as covers change rather than recomputing it. That bookkeeping detail is what keeps the algorithm reliably at O(n³) rather than O(n⁴).

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. Example 4 above walks through this fully.

Full guide with examples: Unbalanced assignment (dummy rows/cols).

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. See Example 3 above for a full numeric walkthrough.

Typical conversion: cost(i,j) = Pmax - profit(i,j) (where Pmax is the largest profit in the matrix).

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

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 are “independent zeros” in the Hungarian algorithm?

Independent zeros are zeros chosen so that no two are in the same row or column. Picking n independent zeros gives a valid one-to-one assignment.

Questions people ask

What is an augmenting path in the Hungarian algorithm?

It’s an alternating chain of primed and starred zeros, built when the current set of starred zeros can’t be directly extended. Flipping every zero along the path (stars become unstarred, primes become starred) increases the number of independent zeros by exactly one, without breaking the “no shared row/column” rule. See the worked mini-example above for a full trace.

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). If you need an authoritative citation, see the sources below.

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).

1. Practice more matrices: assignment problem examples.
2. Unbalanced/dummy modeling: unbalanced assignment.
3. Graph interpretation: bipartite matching & assignment.
4. Python implementation: Hungarian algorithm in Python.