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