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 a minimum 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.