爲什麼Ford-Fulkerson算法需要後邊緣？

Question

爲了找到圖中的最大流量，爲什麼僅僅在沒有考慮後端邊緣的情況下僅使飽和路徑中具有最小邊緣容量的所有增量路徑飽和就足夠了？我的意思是，如果我們假設它是流動的，那麼它有什麼意義呢？

Answer 1

如果您選擇的路徑不是總體流量的一部分，則在執行Ford-Fulkerson算法時需要使用後沿。

As，其中背部邊緣是必要的一個例子，考慮這個流網絡：

s 
/\ 
    a b 
    \/\ 
    c d 
    \/
     t 

假設所有的邊點下來，所有邊緣都有能力1要找到s的流到t 。假設在Ford-Fulkerson的第一次迭代中，你採用s→b→c→t的路徑。此時，你已經將一個單位的流量從s推到t。如果你沒有任何回邊加，你留下了這一點：

s 
/
    a b 
    \ \ 
    c d 
    /
     t 

沒有更多的S-T的路徑，但是，這並不意味着你有一個最大流量。你可以通過沿着路徑s→a→c→t和沿路徑s→b→d→t發送一個流量來將兩個單位的流量從s推到t。在剩餘流量網絡中沒有任何後沿，您永遠不會發現這條其他路徑。

希望這會有所幫助！