最大流量法是一種用於找到網路中最大流量的算法。以下是該算法的主要步驟:
尋找增廣路徑:
從源點開始,尋找一條到匯點的路徑,要求路徑上每條邊的殘量(即邊上的最大流量與當前分配流量的差值)都大於0。這樣的路徑被稱為增廣路徑,因為它還可以分配更多的流量。
確定增廣路徑上的最小殘量:
在找到的增廣路徑上,找到殘量最小的邊,記為flow。這個最小殘量將限制路徑上可以分配的最大額外流量。
通過不斷重複這個過程,直到無法找到新的增廣路徑為止,算法會收斂到一個最大流。這種方法基於Ford-Fulkerson定理,該定理保證了通過不斷尋找增廣路徑並調整流量分配,最終能夠找到網路中的最大流量。