rajiv_kale's blog

By rajiv_kale, history, 3 years ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it