Hungarian Algorithm

An algorithm to find the minimum edge weight matching for an arbitrary bipartite graph.

Description

This algorithm allows you to find the minimum weight matching of a bipartite graph. The graph can be of arbitrary size and connectedness. The edge weights are captured by a MxN weight matrix where an infinite(Inf) weight designates that that pair of vertices given by that position are not connected.

• Acknowledgements: This submission has inspired the following:; Munkres Assignment Algorithm
• MATLAB release: MATLAB 7.2 (R2006a)

[Minh Hoai Nguyen]

This works pretty well. I don't know if it could be faster; It took 63s for a random 400*400 matrix.

[Alan Cramton]

Works great !!! 400 X 400 takes about 32 seconds on 1.6 Ghz Pentium M laptop. And it works. I think this is much better than the other ones posted.

[Jean-Francois Lalonde]

This works pretty well, but I've found that the hungarian.m function part of the Bayes net toolbox (FullBNT) http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html
is approximately twice as fast. It took 17 seconds to process a random 400x400 matrix with the BNT code, whereas this code took 31 sec.

[Richard Brown]

Good:
* works
* easy to use
* plenty of comments
* doesn't require you to convert your graph to have equal numbers of nodes

Bad:
* Potentially speed, although I imagine a large amount more work has gone into the BNT version
* Help section could use an example, and an H1 line

I was thrilled that this was here - it was exactly what I needed, and I got it working with no effort at all, really.

Thanks for sharing it.
    

[ashin mukherjee]

Great job, works pretty fast too.
But aren't there any algorithm for general graphs and not only for bipartite graphs

[anand sunali]

Great Job

[ali hosseinzadeh]

Do you know where i can find a matlab code for maximum weight matching in general graphs?

[Mody Avinash]

Great Job

[zikai wu]

Good Job.

[Peter L]

The Hungarian algorithm was already available here:

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543&objectType=file

This submission even provides a lot more: A brute-force version for reference, suboptimal (but faster) versions and an implementation as a mex-file which is very fast.

[Yi Cao]

I just found the code has a bug when the cost matrix has some inf elements. For example:

D = [Inf Inf 0 2
     0 Inf 3 Inf
     0 Inf 1 Inf
     Inf 0 Inf 0]

Clearly, the optimal match is

0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0

However,

Matching = Hungarian(D) gives

Matching =

0 0 1 0
0 0 0 0
1 0 0 0
0 1 0 0

row 2 and column 4 have not been matched!

[E J]

I hear the author is really hot.

[Gokhan Gulgezen]

The algorithm works pretty well I think but I need to find maximum weight matching of a bipartite graph not minimum.
So can I use this code to find the maximum weight matching of a bipartite graph just multiplying the performance matrix with negative. Is there anyone to help me or provide information for finding maximum weight matching.
Thanks in advance.

Gokhan

[Andrey Kan]

Alexander, thank you for this implementation. It has been useful to me.

I would like to point out to a possible bug.

Input:
8x10 distance matrix:
distMatrix = [

       Inf Inf Inf Inf Inf Inf 5.0000 389.0000 65.0000 Inf
       Inf Inf 481.0000 Inf Inf Inf Inf Inf Inf Inf
       Inf Inf Inf Inf Inf Inf 464.0000 2.0000 200.0000 449.0000
         0 Inf Inf Inf Inf Inf Inf Inf Inf Inf
       Inf Inf Inf 26.0000 122.0000 169.0000 Inf Inf Inf Inf
       Inf 362.0000 Inf Inf Inf Inf Inf 449.0000 Inf 2.0000
       Inf 0 Inf Inf Inf Inf Inf Inf Inf 404.0000
       Inf Inf Inf Inf Inf Inf 260.0000 Inf Inf Inf]

Output:
matching =

     0 0 0 0 0 0 0 0 1 0
     0 0 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 0 1 0 0
     1 0 0 0 0 0 0 0 0 0
     0 0 0 1 0 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 1
     0 1 0 0 0 0 0 0 0 0
     0 0 0 0 0 0 1 0 0 0

Note, that in the input row #2 can only be assigned to column #3, and column #3 can only be assigned to row #2.

However, in the output: matching(2, 3) == 0;

Implementation found at
http://www.mathworks.com/matlabcentral/fileexchange/6543
doesn't have this problem.

Andrey

[hazem s]

very good

[Yi]

nice work