[問題] 匈牙利演算法的複雜度 sandy4444 PTT批踢踢實業坊

[問題] 匈牙利演算法的複雜度

作者: sandy4444 (質樸) 2014-06-11 17:03:33

剛剛學玩學會用來解決二分圖的max cost perfect matching
的匈牙利演算法
複雜度有 O(n^4) 和 O(n^3)(比較難用)
使用過程很漂亮
但是跟其他求 max cost perfect matching 在複雜度和效率比較
是否弱很多
把二分圖轉換成 s-t flow
用每次找最短 augment path 的方法算出來的在速度上還弱(O(n^3))
所以想問的是在慢一個維度下
為什麼大家這麼愛匈牙利演算法???

作者: fenzhang (分帳) 2014-06-11 21:51:00

圖有負權最短路做不到N^2吧雖然可以SPFA一次後重新標號之後每次DXX做到O(N^3)但好像也沒比匈牙利好寫多少

作者: rebaudiana (微甜) 2014-06-11 22:14:00

N^3匈牙利比起費用流, 難度差不多 ?

繼續閱讀

[問題] 分開、組合huadi73 [問題] 無法判定程式終結dharma [問題] ICPC 6036 Stacking Platesmob5566 [問題] 問題的分類dharma Re: [問題] 驗證某數是否為質數是NP問題DJWS Re: [問題] 驗證某數是否為質數是NP問題dharma Re: [問題] 驗證某數是否為質數是NP問題johnathan717 [問題] 驗證某數是否為質數是NP問題dharma [問題] 如何以數學公式及演算法表達程式tree581 [解題]排列組合CFengY