View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Munkres Assignment Algorithm

4.3 | 6 ratings Rate this file 41 Downloads (last 30 days) File Size: 2.69 KB File ID: #20328 Version: 1.0

Munkres Assignment Algorithm


Yi Cao (view profile)


17 Jun 2008 (Updated )

An efficient implementation of the Munkres algorithm for the assignment problem.

| Watch this File

File Information

Munkres algorithm (also known as Hungarian algorithm) is an efficient algorithm to solve the assignment problem in polynomial-time. The algorithm has many applications in combinatorial optimization, for example in Traveling Salesman problem.

There are a few submissions in the File Exchange for the Munkres algorithm. However, most of them are not efficient. Therefore, I decided to develop my own code. By comparing with existing programms, this code is about two to 5 times faster. For instance, for a 400 x 400 random example, this code can solve it in 4 to 6 seconds, whilst other programs have to take about 17 to 35 seconds.


Assignprob.Zip and Functions For The Rectangular Assignment Problem inspired this file.

This file inspired K Best Assignment Algorithm and Lapjv Jonker Volgenant Algorithm For Linear Assignment Problem V3.0.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (17)
18 Nov 2016 umang vaishnav

Hello, Yi Cao

Thank you for uploading Munkres algorithm. However, as this assignment is only for Minimum assignment, If i want to assign for Maximum assignment then what changes needs to be done in your code?

Suppose matrix [2, 4, 6;8, 6, 10;12, 14, 20]

Min. Assignment is 24. But If I want to Max. assignment then?

Thank you in Advance.

15 Oct 2016 mathu Mari

Is it possible for you explain the commands how it is perform here? Need to understand whole program. I m new to matlab and programming.

Comment only
07 Dec 2015 Paul Quinn

Bug: fails for input row vector [5 4 3 1].
Fix(?): validCol = any(validMat, 1); (dimension for any is not specified in the original code for validCol.)

Comment only
31 Oct 2014 Matteo

Matteo (view profile)

Hi people,
I a question about the hungarian algorithm. this algorithm is optimal algorithm for the assignment problem, and the time complexity is O(n^3), right?
But , if the input is the multidimensional matrix, it's possible to use the hungarian algorithm? how does it change the algorithm and the time complexity ?

Comment only
14 Mar 2014 Markus Buehren

Markus Buehren (view profile)

There is another version of this package here:

Comment only
09 Oct 2012 David Manegold

there is no solution for the following matrix?
1 4 Inf
Inf Inf 5
Inf Inf 7
How do I modify such that it provides the
assignment =
1 0 0
0 0 1
0 0 0

Comment only
08 Oct 2012 David Manegold

I have a 15x51 matrix on which this algorithm fails. the JV handles it.

can I send you the matrix

Comment only
20 Apr 2012 Arun Kumar Chithanar

This is much faster than the version 1.0. Thanks!

Comment only
30 Jan 2012 Max

Max (view profile)


i have also a cost matrix which returns zero assignments while the Hungarian ( algorithm works fine...

Comment only
01 Oct 2011 Christoph

29 Sep 2011 Christoph


I have a cost matrix for which this script does not seem to work. It seems to make random assignments where the candidate has maximum costs (inf). Could you help?

Comment only
12 Oct 2010 Jiangmin zhang

but i have a question

is the time complexity of your algorithm on the order of n^3 or n^4?

30 Jun 2010 Kevin Crosby

Kevin Crosby (view profile)


There was a problem with my data, that did not occur in any of my other cases.

Thanks again!


Comment only
24 Jun 2010 Yi Cao

Yi Cao (view profile)


Thanks for comments. I have looked at your problem. Actually, the problem does not have a valid solution. The code you linked does not provide a valid solution either. If you check the solution, you will find many zeros, which means no valid assignment can be done for these positions.


Comment only
22 Jun 2010 Kevin Crosby

Kevin Crosby (view profile)

This is extremely fast compared to the other Hungarian algorithms I've seen posted here.

I have successfully used this many times to optimally connect line segments such that the total cost is minimized.

However, I did find a case in which the assignment matrix does not return any matches, but some of the slower algorithms do.

For example, i got results using Markus Buehren's algorithm at

My distance matrix is found here:

Do you have a quick fix for this?


03 Mar 2010 Zacharias Voulgaris

Truly excellent. It has everything you could ask of a Matlab program: good structure, excellent comments, simplicity, flow and efficiency. Thank you for sharing.

05 Apr 2009 V. Poor

23 Jun 2008

fix a bug

Contact us