The Hungarian algorithm produces the best distribution, with for example: lowest price or shortest time.
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:
$48: Total
The Hungarian Matrix plays with values until the best distribution has only zeroes.
Decrease each left to right line with its lowest value.
0 | 1 | 90 | 15 |
6 | 64 | 0 | 81 |
13 | 14 | 0 | 23 |
40 | 0 | 12 | 55 |
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 |
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.
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.