The Hungarian algorithm allows a "minimum matching" to be found. This can be used in instances where there are multiple quotes for a group of activities and each activity must be done by a different person, to find the minimum cost to complete all of the activities.
1activity" along the top, with the "cost" for each pair in the middle.
2columns if necessary. Conventionally, each element in the dummy row/column is the same as the largest number in the matrix.
3subtracting the minimum value of each row from that row.
5zero elements with the minimum number of lines it is possible to cover them with. (If the number of lines is equal to the number of rows then go to step 9)
10matrix, disregarding dummy rows. This shows who should do which activity, and adding the costs will give the total minimum cost.
Questions and Answers
Give us 3 minutes of knowledge!
|This video explains why the Hungarian algorithm works.|
- If you wish to find a maximum matching rather than a minimum, multiply each number by -1 in step 1, then follow the steps as written.
Things You'll Need
In other languages:
Thanks to all authors for creating a page that has been read 225,403 times.