The Hungarian algorithm

The Hungarian algorithm consists of four main steps. The first two steps are performed once, while Steps 3 and 4 are repeated until an optimal assignment is found. The input to the algorithm is an n × n cost matrix containing only nonnegative values.

Step 1: Subtract the row minima

For each row, identify the smallest element and subtract it from every element in that row.

Step 2: Subtract the column minima

For each column, identify the smallest element and subtract it from every element in that column.

Step 3: Cover all zeros with the minimum number of lines

Cover all zeros in the resulting matrix using the smallest possible number of horizontal and vertical lines. If n lines are required, an optimal assignment can be made among the zeros, and the algorithm stops. If fewer than n lines are needed, continue to Step 4.

Step 4: Create additional zeros

Find the smallest value (denoted k) that is not covered by any line in Step 3. Subtract k from all uncovered elements, and add k to all elements that are covered twice.

Continue with:

The Hungarian algorithm explained using an example

The Hungarian algorithm explained using a self-chosen or random cost matrix