最大流问题之FF算法与EK算法
目錄
問題描述：
EK算法：
算法描述：
偽代碼：
例子：
控制臺對應(yīng)輸出為：
關(guān)鍵定理證明：
最大流最小割定理：
1推2：
2推3：
3推1：
時(shí)間復(fù)雜度分析
分析
關(guān)鍵邊定義：
時(shí)間復(fù)雜度計(jì)算：
FF算法：
FF算法介紹
FF算法缺陷分析：
問題描述：
G=（V，E）是一個(gè)有向圖，其中每條邊（u，v）有一個(gè)非負(fù)的容量值c（u，v），而且如果E中包含一條邊（u，v），那么圖中就不存在它的反向邊。在流網(wǎng)絡(luò)中有兩個(gè)特殊的結(jié)點(diǎn)，源結(jié)點(diǎn)s和匯點(diǎn)t，源結(jié)點(diǎn)s只會(huì)流出不會(huì)流進(jìn)，匯點(diǎn)只會(huì)流進(jìn)不會(huì)流出，我們要求的就是從源結(jié)點(diǎn)流到匯結(jié)點(diǎn)的路徑的值之和的最大值
EK算法：
算法描述：
每次從殘留網(wǎng)絡(luò)中找出一條從源結(jié)點(diǎn)到匯結(jié)點(diǎn)的最短路徑，流選為路徑中的殘存容量，依據(jù)流更新殘存網(wǎng)絡(luò)（將每條邊的殘存容量改為當(dāng)前容量減去流的大小，并添加對應(yīng)的反向邊，邊的容量為流的大小）
重復(fù)選最短路徑，更新殘存網(wǎng)絡(luò)，直到?jīng)]有最短路徑為止
此時(shí)的流累加和即為最大流
?
由于每次要找的是最短路徑，所以需要用BFS找路徑
偽代碼：
例子：
初始圖：
第一次路徑1->2->4->6，流大小：12
更新后圖為：
第二次路徑為1->3->5->6，流大小：4
更新后圖為：
?
第三次路徑為1->3->5->4->6，流大小：7
更新后圖為：
此時(shí)，再也找不到最短路徑，算法結(jié)束，則最大流為：12+4+7=23
?
控制臺對應(yīng)輸出為：
?
關(guān)鍵定理證明：
最大流最小割定理：
| 下面條件等價(jià) 1、f是G的一個(gè)最大流 2、殘存網(wǎng)絡(luò)不包括任何增廣路徑 3、|f|=c(S,T)，其中（S，T）是流網(wǎng)絡(luò)的某個(gè)切割 |
1推2：
假定f是G的一個(gè)最大流，但殘存網(wǎng)絡(luò)中仍包含有一條增廣路徑，那么對流f增加流量后，所得的值是嚴(yán)格大于f的值的，這與f是G的一個(gè)最大流矛盾
2推3：
假設(shè)流網(wǎng)絡(luò)G不包含任何增廣路徑，現(xiàn)在定義S為G中存在一條從s到v的路徑的所有v的集合，定義T為V-S，則劃分（S,T）是流網(wǎng)絡(luò)G的一個(gè)切割。
對S中的任意一個(gè)結(jié)點(diǎn)u，T中的任意一個(gè)結(jié)點(diǎn)v
如果（u,v）屬于E，則必有f(u,v)=c(u,v)
如果(v,u)屬于E，則必有f(v,u)=0
如果（u,v）和(v,u)都不屬于E，則f(u,v)= f(v,u)=0
因此
所以|f| = f(S,T）= c(S,T)，得證
3推1：
對于所有切割（S,T），|f|≤c（S，T）
因此，當(dāng)|f| = c（S，T）時(shí)，f就是一個(gè)最大流
?
時(shí)間復(fù)雜度分析
分析
對于一個(gè)流網(wǎng)絡(luò)，我們要分析EK算法的復(fù)雜度，實(shí)際就是要分析調(diào)用bfs的次數(shù)，但是bfs的次數(shù)是很難分析的，所以需要做一點(diǎn)轉(zhuǎn)換，將對bfs次數(shù)的分析轉(zhuǎn)換為其它和它等價(jià)的實(shí)體量且稍微簡單一點(diǎn)的分析
在實(shí)際分析中，我們發(fā)現(xiàn)關(guān)鍵邊的個(gè)數(shù)和bfs的次數(shù)是等價(jià)的，所以要分析bfs次數(shù)，不妨就分析關(guān)鍵邊的個(gè)數(shù)
?
關(guān)鍵邊定義：
邊(u,v)的殘存容量為最短路徑的殘存容量，則稱為為關(guān)鍵邊
任一增廣路徑都至少存在一條關(guān)鍵邊
?
時(shí)間復(fù)雜度計(jì)算：
邊(u,v)成為關(guān)鍵邊到下一次成為關(guān)鍵邊，從原結(jié)點(diǎn)到u的距離至少增加2個(gè)單位
②由于從源結(jié)點(diǎn)s到結(jié)點(diǎn)u的中間結(jié)點(diǎn)不可能包括s、u或t，所以一直到u成為不可到達(dá)結(jié)點(diǎn)前，距離最長為v-2
由①②可得邊（u,v）成為關(guān)鍵邊的次數(shù)最多為（V-2）/2，取V/2
?
由于一共有E條邊，所以EK算法中關(guān)鍵邊總數(shù)為O（VE）
總時(shí)間 = BFS時(shí)間 * BFS次數(shù)
由于每次BFS時(shí)間為O（E），需要O（VE）次BFS，所以總時(shí)間為O（VE2）
?
?
FF算法：
FF算法介紹
FF算法和EK算法很相似，唯一不同的地方就是FF算法每次找的不是最短增廣路徑，它找的路徑是隨機(jī)的
?
FF算法缺陷分析：
由于FF算法每次找的增廣路徑不是最短路徑，所以FF算法存在這樣一個(gè)缺陷：它會(huì)使一條邊成為關(guān)建邊的最大次數(shù)從原來的V/2上升到K/2（K為所有邊中權(quán)值最大的邊的權(quán)值）
舉下面一個(gè)例子
圖3、FF算法樣例圖
按照EK算法，邊（u,v）和（v,u）成為關(guān)鍵邊的最大次數(shù)應(yīng)該是4/2-1 = 1，所以所需要的bfs次數(shù)為1+1 = 2次
圖4、FF算法過程圖
?
圖5、FF算法過程圖
在FF算法中，它將以圖4和圖5的方式反復(fù)流動(dòng)500000次
邊（u,v）和（v,u）成為關(guān)鍵邊的最大次數(shù)是1000000/2=500000，所以所需要的bfs次數(shù)為500000+500000=1000000次，由于調(diào)用bfs的效率過低，所以會(huì)導(dǎo)致FF算法比EK算法慢
代碼：×
?
總結(jié)
以上是生活随笔為你收集整理的最大流问题之FF算法与EK算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python leetcode_leet
- 下一篇： JS_13原型与原型链