最小割演算法

最小割演算法（Minimum Cut Algorithm）是一種用於解決圖論中最小割問題的算法。最小割問題是指給定一個帶權圖G=(V, E)和一個源點s和一個匯點t，找到一個割（即V的一個劃分，使得s和t屬於不同的集合），使得割中邊的權重總和最小。

最小割演算法有很多種，以下是其中一種基於福特-福爾克曼（Ford-Fulkerson）算法的實現：

1. 初始化：設源點s的殘量網路為G=(V, E)，其中每條邊的容量為無窮大。

2. 增廣路徑搜尋：使用迪傑斯特拉（Dijkstra）算法或類似的方法找到從源點s到匯點t的一條增廣路徑。

3. 增廣：沿著找到的增廣路徑，將路徑上的邊按照逆序進行增廣。每次增廣時，將邊上的流量增加最小流（即路徑上邊的容量的最小值），直到無法增廣為止。

4. 更新殘量網路：如果增廣路徑無法找到，或者增廣後流量達到最大，則停止算法。否則，更新殘量網路，準備進行下一次增廣。

5. 判斷是否達到最大流：如果殘量網路中所有邊的流量都達到最大，則算法結束，輸出最大流。否則，回到步驟2繼續尋找增廣路徑。

這種算法的時間複雜度與增廣路徑的數量有關，而增廣路徑的數量最多為圖中邊的數量。因此，時間複雜度通常是O(VE)，其中V是頂點數，E是邊數。

在實際套用中，最小割問題和最大流問題密切相關，最小割問題的最優解可以通過最大流問題的最優解來得到。因此，通常使用最大流算法（如Edmonds-Karp算法或Push-Relabel算法）來間接解決最小割問題。