### Highlights fromHungarian Algorithm

4.0625

4.1 | 16 ratings Rate this file 133 Downloads (last 30 days) File Size: 9.11 KB File ID: #11609

# Hungarian Algorithm

30 Jun 2006 (Updated 08 Aug 2006)

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

File Information
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 file inspired Munkres Assignment Algorithm.

MATLAB release MATLAB 7.2 (R2006a)
Tags for This File
Everyone's Tags
Tags I've Applied
04 May 2013

nice

18 Apr 2013

Very good work.

03 Oct 2012

This function can effectively calculate NxN matrices, and can also process NxM matrices. But it is a little difficult to understand the source code. Maybe my abilities matter. In sum, it is useful.

25 Apr 2012

nice work

08 May 2011

very good

02 Aug 2010

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

26 Nov 2008

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.

Gokhan

25 Jul 2008

I hear the author is really hot.

25 Jun 2008

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!

09 Jan 2008

The Hungarian algorithm was already available here:

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.

20 Oct 2007

Good Job.

19 Oct 2007

Great Job

02 Aug 2007

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

08 Jul 2007

Great Job

14 Jun 2007

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

04 Jun 2007

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

* 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.

02 Mar 2007

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.

04 Feb 2007

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.

27 Dec 2006

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