我已經為二分圖撰寫了最小匈牙利演算法，使用 Dijkstra 演算法來找到最大匹配的最小成本。但是，我想使用這樣的演算法來實作最大匈牙利演算法，并且不知道僅否定邊緣是否正確，因為我不知道演算法是否會處理它。
我的實作基于以下站點上的解釋：https ://www.ics.uci.edu/~eppstein/163/lecture6b.pdf
給定 G=(AUB, E)，這個想法是通過一個人工起始頂點 s 來標記頂點，該頂點 s 在 A 中具有帶有不飽和節點的邊，并從 s 運行 Dijkstra 演算法以標記每個頂點，然后在標記每個頂點之后，邊緣將通過其原始權重減去邊緣端點的標簽來重新加權。
我已經閱讀了很多文章，我唯一能看到的是，通過否定每個邊，可以以最大成本很好地處理最小匈牙利演算法，但是，我擔心由于 Dijkstra 的演算法不能處理負數邊緣很好，它不會作業。
uj5u.com熱心網友回復：
首先在圖表中找到最大權重。然后否定所有權重并添加最大權重。將原始最大值添加到所有否定值會使它們全部為正。
您也可以使用INT_MAX（或您正在使用的編程語言中的任何等效項）而不是最大權重。這會跳過尋找最大權重的步驟，但可能會使匈牙利演算法的第一次迭代花費更長的時間，或者導致您需要對演算法進行額外的迭代才能獲得結果。無論哪種方式，它可能都沒有太大的區別，并且性能差異將根據圖表中的特定權重而有所不同。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/485816.html
上一篇：在修改它時使用結構陣列遞回
下一篇：for回圈C 內外的值不同