Home > programming, research resources > How to Use the Hungarian Algorithm

How to Use the Hungarian Algorithm


Steps

  1. 1
    Arrange your information in a matrix with the "people" on the left and the "activity" along the top, with the "cost" for each pair in the middle.

    Arrange your information in a matrix with the “people” on the left and the “activity” along the top, with the “cost” for each pair in the middle.

    Arrange your information in a matrix with the “people” on the left and the “activity” along the top, with the “cost” for each pair in the middle.

  2. 2
    Ensure that the matrix is square by the addition of dummy rows/columns if necessary.

    Ensure that the matrix is square by the addition of dummy rows/columns if necessary.

    Ensure that the matrix is square by the addition of dummy rows/columns if necessary. Conventionally, each element in the dummy row/column is the same as the largest number in the matrix.

  3. 3
    Reduce the rows by subtracting the minimum value of each row from that row.

    Reduce the rows by subtracting the minimum value of each row from that row.

    Reduce the rows by subtracting the minimum value of each row from that row.

  4. 4
    Reduce the columns by subtracting the minimum value of each column from that column.

    Reduce the columns by subtracting the minimum value of each column from that column.

    Reduce the columns by subtracting the minimum value of each column from that column.

  5. 5
    Cover the zero elements with the minimum number of lines it is possible to cover them with.

    Cover the zero elements with the minimum number of lines it is possible to cover them with.

    Cover the zero 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)

  6. 6
    Add the minimum uncovered element to every covered element.

    Add the minimum uncovered element to every covered element.

    Add the minimum uncovered element to every covered element. If an element is covered twice, add the minimum element to it twice.

  7. 7
    Subtract the minimum element from every element in the matrix.

    Subtract the minimum element from every element in the matrix.

    Subtract the minimum element from every element in the matrix.

  8. 8
    This example had to be reduced once more

    This example had to be reduced once more

    Cover the zero elements again. If the number of lines covering the zero elements is not equal to the number of rows, return to step 6.

  9. 9
    Select a matching by choosing a set of zeros so that each row or column has only one selected.

    Select a matching by choosing a set of zeros so that each row or column has only one selected.

    Select a matching by choosing a set of zeros so that each row or column has only one selected.

  10. 10
    Notice that D has not been used

    Notice that D has not been used

    Apply the matching to the original matrix, disregarding dummy rows. This shows who should do which activity, and adding the costs will give the total minimum cost.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: