具有單位容量邊緣的流動網絡中的Ford-Fulkerson方法的時間複雜度

Question

Ford-Fulkerson算法是否可以找到單位容量流網絡（所有邊都具有單位容量）的最大流量，其中n頂點和m邊O(mn)時間？

Answer 1

O(M*f)爲福特富爾克森與整數的容量，其中M是邊緣的數量和f最大流量的值的曲線圖的已知運行時間估計，僅僅因爲它很容易找到在每個O(M)增強的路徑，並每條這樣的路徑至少增加1個流量。如果你的圖沒有重複的邊（也就是說，沒有一對邊具有相同的開始和結束頂點），並且每條邊具有單位容量，則最大流程f不超過頂點數量N（僅僅是因爲從源頭不會有超過N-1的邊緣），因此複雜度是確實是O(N*M)。

但是，如果你的圖形，允許有重複的邊緣（但仍每條邊有1容量），然後f可以比N大，最多M，時間複雜度會變得O(M*M)，它是不難發現這種複雜性的例子。