Solving the Assignment Problem with Munkres Algorithm

EDIT: The reasoning for the time complexity of the Munkres Algorithm in this video is incorrect. An extra 0 is not always created each loop iteration which means the loop is executed O(n^2) times. The line drawing can be done in O(n^2) time giving the O(n^4) time.

Here we explain how to use the Munkres Algorithm (also known as the Hungarian Algorithm) to solve the assignment problem. Created as a coursework for Data Structures & Algorithms.

Time Stamps:
0:00 - Introduction
0:37 - Munkres Pseudocode
1:03 - Munkres Example
3:53 - Line Drawing Pseudocode
4:47 - Line Drawing Example
5:45 - Time Complexity of Line Drawing
6:13 - Time Complexity of Munkres
7:25 - Munkres for Unbalanced Matrices
8:21 - Munkres for Maximum Weight Matching

By Josh Anthony and Sam Coward for our Data Structures and Algorithms coursework.

References:
And page 209 of 'Emerging Directions in Embedded and Ubiquitous Computing: EUC 2007 Workshops: TRUST, WSOC, NCUS, UUWSN, USN, ESO, and SECUBIQ, Taipei, Taiwan, December 1-4, 2007, Proceedings'