The Hungarian algorithm is usually a combinatorial optimisation that resolves task difficulties within polynomial time. The first version, referred to as the actual Hungarian method, had been created as well as published by Harold Kuhn in 1955.

## The Hungarian algorithm

The Hungarian algorithm involves the four steps. 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 every row, get the lowest element and also subtract this through every element in that row.

### Step 2: Subtract column minima

In the same way, for every column, get the lowest element and also subtract this through every 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 also vertical lines. If n lines are needed, an optimal assignment exists among the zeros. The algorithm stops.

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

### Step 4: Create additional zeros

Find the smallest element (call it k) that isn't included by a line in Step 3. Subtract k from all uncovered elements, and also add k to all elements that are covered twice.

## The Hungarian algorithm: An example

For example, where four jobs (J1, J2, J3, and J4) have to be performed through four workers (W1, W2, W3, and W4), one job per worker. The matrix below exhibits the price of determining a particular worker to a certain job. The objective is to minimize the entire price from the task.

J1 | J2 | J3 | J4 | |
---|---|---|---|---|

W1 | 82 | 82 | 69 | 92 |

W2 | 77 | 37 | 49 | 92 |

W3 | 11 | 69 | 5 | 86 |

W4 | 8 | 9 | 98 | 23 |

### Step 1: Subtract row minima

We start with subtracting the row minimum from every row. We get the smallest element in the first row is, for example, 69. Therefore, we all subtract 69 from each element in the first row. The resulting matrix will be:

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

In the same way, we subtract the column minimum from every column, providing the next matrix:

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, we will consider the minimum number of lines (the line will be horizontal or even vertical which have to include all zeros in the matrix. All zeros can be included using 3 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 |

Simply because the number of lines needed (3) is lower compared to the size of the matrix (n=4), we continue with Step 4.

### Step 4: Create additional zeros

First, find that the smallest uncovered number is 6. We will subtracting this number from all uncovered elements and also add it to all elements that are covered 2 times. This results in the following matrix:

J1 | J2 | J3 | J4 | |
---|---|---|---|---|

W1 | 7 | 8 | 0 | 2 |

W2 | 40 | 0 | 18 | 40 |

W3 | 0 | 58 | 0 | 60 |

W4 | 0 | 1 | 96 | 0 |

Now we return to Step 3.

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

Again, we consider the minimum number of lines that are required to cover all zeros in the matrix. Now there are 4 lines required:

Simply because the number of lines required (4) equals the size of the matrix (n equal to 4), an optimal assignment exists among the zeros in the matrix. Therefore, the algorithm stops.

### The optimal assignment

The following zeros cover an optimal assignment:

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

Thus, W1 should perform J3, W2 J2, W3 J1, and W4 should perform J4. The total cost of this optimal assignment is to 69 + 37 + 11 + 23 i.e. 140.

Tap to ChatGet instant assignment help

Tap to ChatGet instant assignment help