The Hungarian algorithm

The Hungarian algorithm consists of the four steps below. The first two steps are executed once, while Steps 3 and 4 are repeated until an optimal assignment is found. The input of the algorithm is an n by n square matrix with only nonnegative elements.

Step 1: Subtract row minima

For each row, find the lowest element and subtract it from each element in that row.

Step 2: Subtract column minima

Similarly, for each column, find the lowest element and subtract it from each element in that column.

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

Cover all zeros in the resulting matrix using a minimum number of horizontal and vertical lines. If n lines are required, an optimal assignment exists among the zeros. The algorithm stops.

If less than n lines are required, continue with Step 4.

Step 4: Create additional zeros

Find the smallest element (call it k) that is not covered by a 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 based on an example.

The Hungarian algorithm explained based on a self chosen or on a random cost matrix. uses cookies to provide you with an optimal user experience.

Yes, I accept cookies.

We use techniques including cookies to offer you an optimal user experience. This also allows us to analyze the behavior of visitors and thereby improve our website. Cookies from ourselves and from our partner Google can be used to serve ads, to personalize content, and to provide social media features. We also share information about your use of our site with this partner, who may combine this information with other information that you have provided to them or that they have collected from your use of their services.