繼續福特 - 福爾克森

Question

我想學習福特 - 福爾克森的方法。我已經爲練習做了一個例子，在某些時候我不能繼續增加流量，但我知道流量可能會更高。

首先，我已經加了路徑s -> 1 -> 2 -> t。現在我找不到增加流量的路徑。我知道如果我先通過a -> 1 -> 5 -> 6 -> t，那麼我可以遞增路徑s -> 3 -> 4 -> 2 -> t，但是如果我必須實施它，我不知道該怎麼做。

我在做什麼錯？

Answer 1

我想通了。我不知道可以沿箭頭的相反方向使用邊緣。

所以我們可以遍歷路徑s -> 3 -> 4 -> 2 -> 1 -> 5 -> 6 -> t。

然後我們得到預期的結果。