# Hungarian algorithm

The Hungarian algorithm produces the best distribution, with for example: lowest price or shortest time.

## Best distribution

Example:

Driver Electrician Gardener Manager
Alex \$8 \$9 \$98 \$23
Ben \$11 \$69 \$5 \$86
Chris \$20 \$21 \$7 \$30
Dave \$47 \$7 \$19 \$62

Lowest price:

• \$23: Alex - manager
• \$11: Ben - driver
• \$7: Chris - gardener.
• \$7: Dave - electrician.

\$48: Total

## Steps

The Hungarian Matrix plays with values until the best distribution has only zeroes.

### Step 1, zero in every line left to right

Decrease each left to right line with its lowest value.

• first line: - 8
• second line: -5
• third line: -7
• fourth line: -7.
 0 1 90 15 6 64 0 81 13 14 0 23 40 0 12 55

### Step 2, zero in every top down line

Decrease each top down line with its lowest value, - 15 for last one only.

 0 1 90 0 6 64 0 66 13 14 0 8 40 0 12 40

### Step 3, mark zeroes to keep

Cover all zeroes with the lowest possible number of lines.

 0 1 90 0 6 64 0 66 13 14 0 8 40 0 12 40

Find the lowest unmarked value: 6.

### Step 4, make more zeroes

Increase all values in marked lines with the value from step 3.

 6 7 102 6 6 64 6 66 13 14 6 8 46 6 24 46

Decrease all values with the value from step 3.

 0 1 96 0 0 58 0 60 7 8 0 2 40 0 18 40

Do steps 3 and 4 again and again, until you have enough zeroes.