← Home · Hungarian algorithm, four ways
Hungarian algorithm
Same idea, four ways to study it. Tap a style and find the one that clicks for you. 📺 Prefer to watch? Videos are on the lesson page.
🧩 Match workers to jobs for the lowest total cost. The recipe: row reduce → column reduce → cover zeros with fewest lines → assign.

What it is

An assignment problem: n workers, n jobs, a cost for each pairing. One job per worker, one worker per job. The Hungarian algorithm finds the matching with the smallest total cost by reducing the cost table until the answer shows up as zeros.

The recipe

row reduce → column reduce → cover zeros → assign
  1. Subtract each row's smallest from that row.
  2. Subtract each column's smallest from that column.
  3. Cover all zeros with the fewest lines.
  4. If lines = n → assign (one zero per row & column). If lines < n → adjust, then re-cover.

Adjustment: smallest uncovered number, subtract it from all uncovered, add it to any number covered twice.

Worked example

3×3 costs reduce to the table below; the zeros cover with 3 lines, so we assign.

Reduced + assign
J1J2J3
W1005
W2077
W3650

W1 → J2, W2 → J1, W3 → J3. Cost from the original table: 11 + 6 + 6 = $23.

Watch out

• Read the final cost off the original table, the reducing was just to find the pairing.
• You can only assign when the covering lines equal n.
• Each assignment uses one zero per row and per column.
• If lines < n, do the adjustment, don't force an assignment.

Row reduce, then column reduce

Original
J1J2J3
W191114
W261513
W312136
Row reduce
J1J2J3
W1025
W2097
W3670
Column reduce
J1J2J3
W1005
W2077
W3650

Each reduction makes more zeros. Once the zeros need n lines to cover, you can read off one zero per row and column.

The assignment

Gold zeros = the chosen pairings: W1 → J2, W2 → J1, W3 → J3. One per row, one per column. Total from the original table = $23.

Warm up first

Don't read yet, just have a go in your head:

What are steps 1 and 2?
Row reduce then column reduce, subtract the smallest in each row, then each column.
You cover a 3×3's zeros with 3 lines. Assign yet?
Yes, 3 lines = n = 3, so an assignment exists.
Where do you read the final cost from?
The original cost table, not the reduced one.

Faded example: row reduction

Rung 1 · watch one done fully

Row W1 is 9, 11, 14. Smallest is 9. Subtract: 0, 2, 5.

Rung 2 · you fill the gaps

Row W3 is 12, 13, 6. Smallest is 6. Subtract 6: 6, 7, ? → the new row is 6, 7, ?

Check my gaps
6, 7, 0.
Rung 3 · all you

After row reduction the column 2 entries are 2, 9, 7. Column reduce this column (subtract its smallest). What does it become? Check below.

Check my answer
Smallest in column 2 is 2. Subtract 2: the column becomes 0, 7, 5.

Say it back

In one sentence, out loud: when are you allowed to make the assignment?

⚡ Hungarian algorithm, one look

Goalmatch n workers to n jobs for least total cost
Step 1row reduce (subtract each row's smallest)
Step 2column reduce (subtract each column's smallest)
Step 3cover all zeros with the fewest lines
Assign whennumber of lines = n (one zero per row & column)
If lines < nsmallest uncovered: − from uncovered, + to double-covered
Costread off the ORIGINAL table (e.g. 11+6+6 = 23)
Trapfinal cost = original table · only assign when lines = n