Explaination needed for e-maxx implementation of Hungarian Algorithm

Правка en3, от Mr_No_One, 2020-12-09 00:36:04

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

Теги hungarian algorithm, bipartite matching, emaxx

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Mr_No_One 2020-12-09 00:36:04 3
en2 Английский Mr_No_One 2020-12-08 22:36:33 7
en1 Английский Mr_No_One 2020-12-08 22:32:56 1680 Initial revision (published)