Logo HungarianAlgorithm.com

Solve an assignment problem online

Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.

Fill in the cost matrix (random cost matrix):

Size: 3x3 4x4 5x5 6x6 7x7 8x8 9x9 10x10



Solution

This is the cost matrix.

215674741171769836
2429986682877736
428178677061568784
296211502194217
462794669780175890
1593284637587420
16518334054514964
13434634379702688
9590665889892444

Subtract row minima

For each row, the minimum element is subtracted from all elements in that row.

10456363060658725(-11)
2126956379847403(-3)
03936252819144542(-42)
286100492093206(-1)
29107749806304173(-17)
0583183626577319(-1)
11013283549464459(-5)
9030593975662284(-4)
4085615384841939(-5)

Subtract column minima

For each column, the minimum element is subtracted from all elements in that column.

10456363054658722
2126956379787400
03936252813144539
286100491493203
29107749805704170
0583183620577316
11013283543464456
9030593969662281
4085615378841936
(-6)(-3)

Cover all zeros with a minimum number of lines

A total of 7 lines are required to cover all zeros.

10456363054658722x
2126956379787400x
03936252813144539x
286100491493203x
29107749805704170x
0583183620577316x
11013283543464456
9030593969662281
4085615378841936
x

Create additional zeros

The number of lines is smaller than 9. The smallest uncovered element is 4. We subtract this value from all uncovered elements and add it to all elements covered twice.

10496363054658722
2130956379787400
04336252813144539
286500491493203
29147749805704170
0623183620577316
709243139424052
5026553565621877
0081574974801532

Cover all zeros with a minimum number of lines

A total of 7 lines are required to cover all zeros.

10496363054658722x
2130956379787400x
04336252813144539
286500491493203x
29147749805704170x
0623183620577316x
709243139424052
5026553565621877
0081574974801532
xx

Create additional zeros

The number of lines is smaller than 9. The smallest uncovered element is 9. We subtract this value from all uncovered elements and add it to all elements covered twice.

19586363054658722
3039956379787400
043271619453630
377400491493203
38237749805704170
9713183620577316
700152230333143
501746265653968
007248406571623

Cover all zeros with a minimum number of lines

A total of 8 lines are required to cover all zeros.

19586363054658722x
3039956379787400x
043271619453630
377400491493203x
38237749805704170x
9713183620577316x
700152230333143x
501746265653968
007248406571623
xx

Create additional zeros

The number of lines is smaller than 9. The smallest uncovered element is 4. We subtract this value from all uncovered elements and add it to all elements covered twice.

23626363054658722
3443956379787400
043231215013226
417800491493203
42277749805704170
13753183620577316
1140152230333143
501342225249564
006844366167219

Cover all zeros with a minimum number of lines

A total of 8 lines are required to cover all zeros.

23626363054658722x
3443956379787400x
043231215013226
417800491493203x
42277749805704170x
13753183620577316
1140152230333143x
501342225249564
006844366167219
xxx

Create additional zeros

The number of lines is smaller than 9. The smallest uncovered element is 1. We subtract this value from all uncovered elements and add it to all elements covered twice.

24636363055658722
3544956379797400
043221114003125
427900491593203
43287749805804170
13753082610567215
1250152231333143
501241215248463
006743356166118

Cover all zeros with a minimum number of lines

A total of 8 lines are required to cover all zeros.

24636363055658722x
3544956379797400x
043221114003125
427900491593203x
43287749805804170
13753082610567215
1250152231333143x
501241215248463
006743356166118
xxxx

Create additional zeros

The number of lines is smaller than 9. The smallest uncovered element is 1. We subtract this value from all uncovered elements and add it to all elements covered twice.

25646363056668722
3645956379807500
043211013003024
438000491694203
43287648795804069
13752981600567114
1360152232343143
501140205248362
006642346166017

Cover all zeros with a minimum number of lines

A total of 9 lines are required to cover all zeros.

25646363056668722x
3645956379807500x
043211013003024x
438000491694203x
43287648795804069x
13752981600567114x
1360152232343143x
501140205248362x
006642346166017x

The optimal assignment

Because there are 9 lines required, an optimal assignment exists among the zeros.

25646363056668722
3645956379807500
043211013003024
438000491694203
43287648795804069
13752981600567114
1360152232343143
501140205248362
006642346166017

This corresponds to the following optimal assignment in the original cost matrix.

215674741171769836
2429986682877736
428178677061568784
296211502194217
462794669780175890
1593284637587420
16518334054514964
13434634379702688
9590665889892444

The total minimum cost is 130.


HungarianAlgorithm.com © 2026. All rights reserved.
Part of Echion, KvK 50713795, BTW NL001446762B10.