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 $30Dave $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.

Step 2, zero in every top down line
Decrease each top down line with its lowest value, - 15 for last one only.

Step 3, mark zeroes to keep
Cover all zeroes with the lowest possible number of lines.
 0  1 90  06   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  7102 66   64     6 6613 14       6 8 46 6 24 46 
Decrease all values with the value from step 3.
 0  1 96 00   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
 hungarianalgorithm.com, step by step examples of the Hungarian Algorithm.

Category:Algorithms