Explaination needed of e-maxx implementation of Hungarian Algorithm

Revision en2, by Mr_No_One, 2020-12-08 22:36:33

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)


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


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