Hungarian algorithm
combinatorial optimization algorithm for the assignment problem
The Hungarian algorithm produces the best distribution, with for example: lowest price or shortest time.
Best distribution change
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 change
The Hungarian Matrix plays with values until the best distribution has only zeroes.
Step 1, zero in every line left to right change
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 change
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 change
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 change
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.
Other websites change
- hungarianalgorithm.com, step by step examples of the Hungarian Algorithm.