Explaination of e-maxx implementation of Hungarian Algorithm

Revision en1, by rajiv_kale, 2020-12-08 22:32:56

I have gone through the following materials to learn all the prerequisits to understand the algorithm but still this specific implementation(e-maxx) is difficult to understand. So if anyone can give its explaination then it will be helpful not only to me but to lot more people who will see it in the future as the problem hungarian algorithm for solving assignment problem looks common.

Main algorithm, whose implementation i am finding a bit difficult to understand (use google translator if necessary) The best part of this implementation is that its code is only 30 lines long and it runs in O(n*n*n)

http://e-maxx.ru/algo/assignment_hungary



Good lectures on hungarian algorithm

*.) https://www.youtube.com/watch?v=Wq2tkITYYHE - part 1 of hungarian algorithm ( full lecture)

*.) https://www.youtube.com/watch?v=jZbbayUurSw - part 2 of hungarian algorithm ( till 36:13).



The resources I have gone through to understand prerequisits

*.) https://www.youtube.com/watch?v=HWHjQdNC-7Y - to understand bipartite graph and what is maximum matching

*.) https://www.youtube.com/watch?v=chdr2aj4FUc - matching in general

*.) https://www.youtube.com/watch?v=IQZEURSSr30 - augmented path and how does matching algorithms works in general(i.e. start with 0 cardanility and keeps on increasing cardanality till it reaches M)

*.) https://www.youtube.com/watch?v=opchRZO2YkE - berge's lemma, a matching in a graph is maximum iff there is no augmented path in the graph.

*.) http://e-maxx.ru/algo/kuhn_matching - kuhn's algorithm

Tags hungarian algorithm, bipartite matching, emaxx

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rajiv_kale 2020-12-09 00:36:04 3
en2 English rajiv_kale 2020-12-08 22:36:33 7
en1 English rajiv_kale 2020-12-08 22:32:56 1680 Initial revision (published)