Hungarian Assignment Minimum Cost

Problem

Solve the square assignment problem with the Hungarian algorithm and return the minimum total cost.

cost[i][j] is the cost of assigning worker i to job j; the algorithm maintains dual potentials and grows a shortest augmenting path for each new row. n is small. Return the minimum sum over perfect matchings.

Hint

The potentials keep reduced costs non-negative so each row can be matched with label updates.

Test cases

case 1

in: [[[1,2,3],[3,1,2],[2,3,1]]]

expected: 3

case 2

in: [[[4,1,3],[2,0,5],[3,2,2]]]

expected: 5

case 3

in: [[[7]]]

expected: 7

case 4

in: [[[1,5,5],[5,1,5],[5,5,1]]]

expected: 3

case 5

in: [[[2,1],[1,2]]]

expected: 2

Starter codePython

def hungarian_assignment(cost):
    # Your code here
    pass

5 test cases · run your code against them in the editor