作者sandy4444 (質樸)
看板Prob_Solve
標題[問題] 匈牙利演算法的複雜度
時間Wed Jun 11 17:03:33 2014
剛剛學玩學會用來解決二分圖的max cost perfect matching
的匈牙利演算法
複雜度有 O(n^4) 和 O(n^3)(比較難用)
使用過程很漂亮
但是跟其他求 max cost perfect matching 在複雜度和效率比較
是否弱很多
把二分圖轉換成 s-t flow
用每次找 最短 augment path 的方法算出來的在速度上還弱(O(n^3))
所以想問的是在慢一個維度下
為什麼大家這麼愛匈牙利演算法???
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.69.191.1
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1402477415.A.014.html
1F：推 fenzhang:圖有負權最短路做不到N^2吧 06/11 21:51
2F：→ fenzhang:雖然可以SPFA一次後重新標號之後每次DXX做到O(N^3) 06/11 21:58
3F：→ fenzhang:但好像也沒比匈牙利好寫多少 06/11 21:58
4F：推 rebaudiana:N^3匈牙利比起費用流, 難度差不多 ? 06/11 22:14