The Hungarian algorithm: An example

Consider an example where four jobs (J1, J2, J3, and J4) must be carried out by four workers (W1, W2, W3, and W4), with each worker assigned to exactly one job. The matrix below shows the cost of assigning each worker to each job. The goal is to minimize the total assignment cost.

	J1	J2	J3	J4
W1	82	83	69	92
W2	77	37	49	92
W3	11	69	5	86
W4	8	9	98	23

Below we explain the Hungarian algorithm step by step using this example. A general description of the algorithm can be found here.

Step 1: Subtract row minima

For each row, find the smallest element and subtract it from every element in that row. For example, the smallest element in the first row is 69, so we subtract 69 from each element in that row.

	J1	J2	J3	J4
W1	13	14	0	23	(-69)
W2	40	0	12	55	(-37)
W3	6	64	0	81	(-5)
W4	0	1	90	15	(-8)

Step 2: Subtract Column Minima

Next, find the smallest element in each column and subtract it from every element in that column. The resulting matrix is:

	J1	J2	J3	J4
W1	13	14	0	8
W2	40	0	12	40
W3	6	64	0	66
W4	0	1	90	0
				(-15)

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

Now, cover all zeros in the matrix using the smallest possible number of horizontal and vertical lines. All zeros can be covered using three lines:

	J1	J2	J3	J4
W1	13	14	0	8
W2	40	0	12	40	x
W3	6	64	0	66
W4	0	1	90	0	x
			x

Because the number of lines (3) is less than the matrix size (n = 4), we continue with Step 4.

Step 4: Create additional zeros

Find the smallest uncovered element, which is 6. Subtract this value from all uncovered elements and add it to all elements that are covered twice. The updated matrix becomes:

	J1	J2	J3	J4
W1	7	8	0	2
W2	40	0	18	40
W3	0	58	0	60
W4	0	1	96	0

We then return to Step 3.

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

We repeat Step 3. This time, four lines are required to cover all zeros:

	J1	J2	J3	J4
W1	7	8	0	2	x
W2	40	0	18	40	x
W3	0	58	0	60	x
W4	0	1	96	0	x

Since the number of lines (4) equals the matrix size (n = 4), an optimal assignment exists among the zeros. The algorithm stops here.

The optimal assignment

An optimal zero assignment is:

	J1	J2	J3	J4
W1	7	8	0	2
W2	40	0	18	40
W3	0	58	0	60
W4	0	1	96	0

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

	J1	J2	J3	J4
W1	82	83	69	92
W2	77	37	49	92
W3	11	69	5	86
W4	8	9	98	23

Thus, worker 1 should be assigned to job 3, worker 2 to job 2, worker 3 to job 1, and worker 4 to job 4. The total minimum cost is 69 + 37 + 11 + 23 = 140.