講解FF算法

感謝王老師！

Ford-Fulkerson算法

這個算法很慢，但是是可以得到正確的結(jié)果的。

下面我用實例來解釋一下這個算法：

與之前的初始的可能有缺陷的找出最大流的算法相似，之前的三步都是先隨便找出一條路徑，然后計算出最小的路徑的權(quán)值，更新閑置圖。但是第四步是這個算法的突出：添加一個反向邊?！簿褪菍⒌谝徊竭x中的路徑中添加一系列綠色的反向邊，各個反向綠色邊的權(quán)值分別等于之前減去的邊的權(quán)值。

在后續(xù)再找新的邊的時候，也需要考慮相應的綠色邊作為可以走過的路徑片段，產(chǎn)生綠色邊的過程中會有平行邊，因此需要將平行邊合并。這里要注意 的是綠色邊和原先的邊的性質(zhì)是相同的，是可以當作一樣的路徑使用的。！

算法的時間復雜度是O(邊數(shù)*最大流數(shù)量)

**************************************************

啊可以幫忙解釋一下嗎我還是沒懂為什么不是所有443邊都減？

綠色的邊代表的是之前選中的路徑的反悔的內(nèi)容(舉個例子 在第一次循環(huán)的時候要添加從v4到v1的綠色邊，權(quán)值是3，也就是說 我在占用從v1到v4空閑值為3的水流之后，我并不能確認這3份的空閑值都需要用到從v1到v4的路徑上，所以保險起見，我需要畫出從v4到v1權(quán)值為3的綠色的邊作為我反悔的內(nèi)容)，

第三輪循環(huán)之前的圖像

那么在第三輪循環(huán)，

只有s->v2->v4->v1->v3->t這一條路徑可以選擇，中間的v4->v1的綠色邊的權(quán)值變?yōu)? ，意思是說 “我認為原先從v1到v4流量為3的這種情況，流量設置的太多了，我返回一個單位的流量 ，將從v1到v4的權(quán)值為3的流量減少為2。至于減少的這一份流量放在了哪里？ 我根據(jù)后續(xù)添加的第三輪反向的綠線可以知道，這一份流量被安置在了從 v1到v3的路徑上，” 那么為什么 從s到v1的4這個數(shù)值不用減一呢？ 是因為在第三次循環(huán)的路徑上，根本就沒有涉及到s->v1的這個路徑。

其實我更想把第三次循環(huán)看成是將s->v1的四份水的流量，原先一開始是直接將其中的三份流量全部一股腦的送到v1到v4這個路徑上去，后來發(fā)現(xiàn)其實將這三份的流量截出來一份的流量運到v1到v3的路徑上更好，從這角度來說 s->v1的路徑上的4份流量就不應該減一。