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.
External links
- hungarianalgorithm.com, step by step examples of the Hungarian Algorithm.