Hungarian algorithm: Difference between revisions

Revision as of 15:11, 15 March 2023

Revision as of 15:24, 15 March 2023

Line 9:

=== Example ===

In this simple example, there are three workers: PaulAlice, Dave,Bob and ChrisDora. One of them has to clean the bathroom, another sweep the floors and the third washes the windows, but they each demand different pay for the various tasks. The problem is to find the lowest-cost way to assign the jobs. The problem can be represented in a [[Matrix (mathematics)|matrix]] of the costs of the workers doing the jobs. For example:

:{| class="wikitable" borderstyle="1text-align:center;"

|-

! {{diagonal split header|Worker    |Task}}

! Clean<br />bathroom

! Sweep<br />floors

! Wash <br />windows

|-

! PaulAlice

| $28

| $34

| $37

|-

! DaveBob

| $35

| $2

| $3

|-

! ChrisDora

| $39

| $34

| $28

|}

The Hungarian method, when applied to the above table, would give the minimum cost: this is $615, achieved by having PaulAlice clean the bathroom, DaveDora sweep the floors, and ChrisBob wash the windows.

=== Matrix formulation ===