網(wǎng)絡最大流問題算法研究【畢業(yè)論文】

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　網(wǎng)絡最大流問題算法研究</p><p>　　所在學院 </p><p>　　專業(yè)班級 數(shù)學與應用數(shù)學

2、 </p><p>　　學生姓名 學號 </p><p>　　指導教師 職稱 </p><p>　　完成日期 年 月 </p><p><b>　　摘要</b></p>

3、<p>　　網(wǎng)絡最大流問題是一個應用極為廣泛的問題, 在交通運輸系統(tǒng)和金融系統(tǒng)中都有廣泛應用, 網(wǎng)絡最大流是計算機科學和運籌學的重要內(nèi)容. 20世紀50年代, 由福特(Ford)、富克遜（Fulkerson）建立的“網(wǎng)絡流理論”成為網(wǎng)絡應用的重要組成部分. 最近幾十年來關(guān)于網(wǎng)絡最大流方面的研究有很大進展, 研究成果也是層出不窮, 本文基于以往學者的研究成果上對網(wǎng)絡最大流問題進行了分析與總結(jié), 并給出了網(wǎng)絡最大流算法中標號算

4、法的求解過程, 也涉及在實際生活中的應用. 最后介紹了現(xiàn)在流行的一些最大流主要算法和實例.</p><p>　　關(guān)鍵詞: 網(wǎng)絡最大流; 標號; 增廣鏈; 算法</p><p>　　Network maximal-flow problem research</p><p><b>　　Abstract</b></p><p&g

5、t;　　Network maximum flow problem is a wide range of applications problem. It is widely used in transportation systems and financial systems, the network maximum flow is an important computer science and operations resear

6、ch content. The "Network Flow Theory", established by Ford and Fulkerson in 1950 has become an important part of network applications. In recent decades the maximum flow on the network of research has made grea

7、t progress, the achievements are fruitful, this dissertation is based on t</p><p>　　Keywords: Maximum network flow; Labeling algorithm; Augmented chain Algorithm</p><p><b>　　目錄</b>&

8、lt;/p><p><b>　　摘要I</b></p><p>　　AbstractII</p><p>　　1 前言……………1</p><p>　　2 理論基礎(chǔ)……………………………………………………………………………...………..3</p><p>　　2.1 相關(guān)定義3</p

9、><p>　　2.2 最大流最小割定理5</p><p><b>　　3標號算法7</b></p><p>　　3.1 標號過程7</p><p>　　3.2 調(diào)整過程7</p><p>　　3.3 標號算法的matlab實現(xiàn)……………………………………………………………...8<

10、;/p><p>　　3.4 標號法應用舉例…………………………………………………………………….....9</p><p>　　4 網(wǎng)絡最大流其他算法簡要介紹…………………………………………………….........15</p><p>　　5 小結(jié)…………………………………………………………………………………………...19</p><p>

11、<b>　　參考文獻20</b></p><p><b>　　致謝21</b></p><p><b>　　1 前言</b></p><p>　　網(wǎng)絡最大流應用非常廣泛, 在交通運輸網(wǎng)絡中有人流、車流、貨物流, 供水網(wǎng)絡中有水流, 金融系統(tǒng)中有現(xiàn)金流, 通訊網(wǎng)絡中有信息流等. 還用于求電力傳輸問題

12、、供銷通路問題中的最大流.</p><p>　　最大流問題已經(jīng)有幾十年的研究歷史, 在這幾十年中, 人們建立了最大流問題比較完善的理論, 從Ford和Fulkerson提出第一個最大流算法到現(xiàn)在, 很多學者都對其進行了改進并提出了很多新的算法, 同時開發(fā)出了大量優(yōu)秀的算法, 如Ford和Fulkerson增截軌算法、 Dinic阻塞流算法、Goldberg推進和重標號算法以及Goldberg和Rao的二分長度阻塞

13、流算法等等, 這些經(jīng)典算法及其中用到的相關(guān)技術(shù)對網(wǎng)絡最大流問題的研究和發(fā)展起到了非常重要的推動作用. 近年來, 隨著網(wǎng)絡和計算機科學的飛速發(fā)展, 最大流問題得到了更深的研究. 多年來, 盡管在眾多學者的共同努力下最大流問題的研究取得了極大的進展, 但是關(guān)于最大流問題的研究還遠遠沒有結(jié)束. 首先, 在理論算法研究方面, 還沒有發(fā)現(xiàn)最大流問題算法時間復雜度的精確下界, 更沒有任何一種通用算法達到或接近問題的下界; 其次, 在算法的實際性能方

14、面, 目前算法的實際性能也不能滿足很多應用問題的需求. </p><p>　　最大流算法的研究過程中最早是Dantzig提出的網(wǎng)絡單純形法和Ford和Fulkerson的增載軌算法, 他們都是偽多項式算法. 20世紀70年代出現(xiàn)了多項式時間算法, 分別由Dinic、Edmonds和Karp等提出. 從最大流問題的提出到現(xiàn)在的發(fā)展, 其中出現(xiàn)了很多優(yōu)秀的算法, 其中增載軌算法、預流推進算法的貢獻比較突出, 基本上很

15、多算法都是基于這兩種算法的基礎(chǔ)上得到的, 其他的算法還包括線性規(guī)劃算法、隨機算法等. 算法的發(fā)展過程中, 先后引入了剩余網(wǎng)絡、增載軌、層次網(wǎng)絡等概念, 對最大流問題的發(fā)展起了很大的推動作用.</p><p>　　對于一個網(wǎng)絡最大流問題, 現(xiàn)在有很多求解方法, 如重標號算法、預流推進算法等. 對一個最大流問題也可以用線性規(guī)劃方法求解, 也就是說, 將一個最大流問題轉(zhuǎn)化為一個線性規(guī)劃模型, 再用單純形法求解. 有些情

16、況下運用線性規(guī)劃模型求解很方便, 而且易于理解.</p><p>　　這幾十年來, 很多著名學者開發(fā)出了很多優(yōu)秀的算法, 由R. K. Ahuja和B. Orlin提出的快速算法是基于Goldberg和Tarjan的算法而得到的一個平行算法, 即預流推進算法. 其對后面學者的研究起了很大的指導作用. 在具有適宜整數(shù)邊容量的稀疏圖中, Gabow的縮進算法是最好的. 而基于Dinic算法結(jié)構(gòu)的那些算法中, 唯一的一

17、個平行算法是由Shiloach和Vishkin給出. Goldberg給出了基于Karzanov預流思想的新算法, 即在剩余網(wǎng)絡中尋找最短路徑. Gallo和Tarjan等提出通過重優(yōu)化技術(shù)能解決參數(shù)最大流中的很多問題, 其是對Goldberg和Tarjan的推重標號法進行的拓展, 進一步優(yōu)化了最大流問題算法.</p><p>　　由Ford和Fulkerson提出的增廣鏈算法是基礎(chǔ), Edmonds和Karp

18、提出的另外一個方法是始終沿著最短路徑增廣, 它利用的是廣度優(yōu)先搜索思想, 這種算法存在一個最壞運行時間. 還有Dinic獨自提出的最短路徑增廣等算法, 這些都對最大流問題的算法研究產(chǎn)生了巨大的影響.</p><p>　　最近也有很多關(guān)于無向網(wǎng)絡最大流問題的研究, 而且發(fā)展迅速, 但是本文主要講述的是有向網(wǎng)絡圖中最大流問題的算法及其應用, 并不涉及無向網(wǎng)絡流算法問題. 下面簡要介紹一下本文的大概內(nèi)容: 本文第一部分

19、介紹與網(wǎng)絡最大流問題有關(guān)的定義及定理, 第二部分介紹最常見的網(wǎng)絡最大流算法—標號算法, 第三部分簡要介紹網(wǎng)絡最大流問題算法中比較流行的幾種其他算法, 后面一部分對本文講述的算法及舉例進行總結(jié). 最后一部分是致謝.</p><p><b>　　2 理論基礎(chǔ)</b></p><p><b>　　2.1 相關(guān)定義</b></p><

20、;p>　　最大流問題是一類應用極為廣泛的問題. 在實際應用中, 從公司配送網(wǎng)絡中求工廠到客戶的流量到求交通網(wǎng)絡中的最大車流量都是最大流問題. 盡管最大流問題中僅有一個發(fā)點和一個收點, 但是, 在實際應用中, 流可能來自多點, 并終于多點. 例如一個公司的配送網(wǎng)絡通常有多個工廠和多個客戶. 生活中這類問題很多, 但是要研究最大流問題, 就需要了解有關(guān)的概念.（定義2.7和定義2.8是與第4節(jié)中新算法有關(guān)定義）</p>

21、<p>　　定義2.1 所有流經(jīng)網(wǎng)絡（有向且連通）的流都起源于同一點, 叫發(fā)點（源）, 終止于另一點叫收點（匯）. 剩余的其他點叫中間點. </p><p>　　定義2.2 設為一個賦權(quán)連通的有向圖, 如果對于每一條弧均有一個非負實數(shù)與之對應, 稱為弧的容量. 表示該弧的最大容量, 簡稱弧容量. 在中指定一個發(fā)點和一個收點, 中其他點是中間點, 這樣的圖叫做容量網(wǎng)絡, 記作.</p>

22、<p>　　定義2.3 設給定容量網(wǎng)絡圖, 將滿足下列兩個條件的流稱為可行流.</p><p><b>　?。ㄈ萘考s束）.</b></p><p>　　對任意（為中間點集）, 有</p><p><b>　　,</b></p><p>　　即中間點的物資輸入量與輸出量相等.<

23、;/p><p>　　對于發(fā)點與收點, 有</p><p><b>　?。ㄆ胶饧s束）,</b></p><p>　　則稱為發(fā)點的總流量, 即容量網(wǎng)絡的總流量.</p><p>　　定義2.4 設有容量網(wǎng)絡, 為發(fā)點, 為收點, 如果把分成兩個非空集合,(), 使, 則所有始點屬于, 而終點屬于的弧的集合, 稱為由決定的割集（截

24、集）, 記作. 割集中所有弧的容量之和, 稱為這個割集的容量, 記為. </p><p>　　定義2.5 設為可行流, 對任意, 分別稱</p><p>　　為的流出量與流入量, 若記</p><p><b>　　,</b></p><p>　　稱為的凈流出量, 簡稱為的流量. </p><p>

25、;　　定義2.6 增廣鏈</p><p>　　對容量網(wǎng)絡,若為網(wǎng)絡中從到的一條鏈（即不考慮每條弧的方向）, 定義的方向為從到, 上的凡是與方向相同的弧稱為前向弧, 凡與方向相反的弧稱為后向弧, 其集合分別用和表示, 若為網(wǎng)絡中從到的一條鏈, 是一個可行流, 如果滿足</p><p>　　則稱為從到的（關(guān)于的）一條增廣鏈.</p><p>　　定義2.7 一致鏈&

26、lt;/p><p>　　若是網(wǎng)絡中連接發(fā)點和收點的一條鏈, 對于（其中為網(wǎng)絡中的弧）, , 則稱是從到的一條一致鏈.</p><p>　　定義2.8 極大一致鏈</p><p>　　設是網(wǎng)絡中連接發(fā)點和收點的一條一致鏈, 也是網(wǎng)絡中連接發(fā)點和收點的一條鏈, 是兩條鏈的公共點的集合, 若對于 且 都有表示從到的容量）, 則稱是網(wǎng)絡中從發(fā)點到收點的一條極大一致鏈.<

27、/p><p>　　2.2 最大流最小割定理</p><p>　　最大流最小割定理由Ford和Fulkerson提出, 所以也叫Ford-Fulkerson定理, 它是網(wǎng)絡最大流問題中一個非常重要的定理, 下面是對最大流最小割定理的介紹:</p><p>　　定理 1 設為網(wǎng)絡的任一可行流, 流量為, 為分離, 的任一割集, 則有.</p><p&g

28、t;　　上面的定理說明網(wǎng)絡中可行流的流量以的割集的最小容量為上界, 而割集的容量又以可行流的最大流為下界. 如果網(wǎng)絡上的一個可行流和網(wǎng)絡中的一個割集, 滿足條件, 那么一定是上的最大流, 而一定是的最小割集.</p><p>　　定理 2(Ford-Fulkerson定理) 在任何網(wǎng)絡中, 從到得最大流的流量等于分離, 的最小割集的容量. （也稱最大流-最小割定理）</p><p>　　證

29、明: 設為的一個最大流, 流量為, 首先定義點集, 滿足如下條件:</p><p><b>　　;</b></p><p>　　, 且, 令, 則弧為非飽和弧;</p><p>　　若, 且, 令, 則弧為非零弧.</p><p>　　因而, 否則若, 則有從到的鏈, 對中的前向弧, 必有, 后向弧必有. 把修改為, 即

30、令</p><p><b>　　而, 其中</b></p><p>　　顯然. 可驗證仍為的一個可行流, 但的總流量等于的流量加上, 這與為最大流矛盾. 故, 從而得到的一個割集, , 且對, 顯然有</p><p><b>　　其次有</b></p><p><b>　　,</b&

31、gt;</p><p><b>　　即. 定理得證.</b></p><p>　　在得到最大流時, 同時也得到了一個最小割集, 這一最小割集對分析網(wǎng)絡有重要意義.</p><p><b>　　3 標號算法</b></p><p>　　標號法是從網(wǎng)絡中的一個可行流出發(fā)（如果中沒有可行流, 可以令是零流

32、）, 運用標號法, 經(jīng)過標號過程和調(diào)整過程, 可以得到網(wǎng)絡中的一個最大流. 下面具體看看標號法的標號過程.</p><p><b>　　3.1 標號過程</b></p><p>　　第一步 給發(fā)點標號</p><p>　　第二步 取一個已標號的點, 對于的一切未標號的鄰接點按下列規(guī)則處理：</p><p>　　如果弧

33、（即為始點, 為終點）, 且 那么給標號其中</p><p>　　如果?。礊槭键c, 為終點）, 且 那么給標號其中</p><p>　　第三部 轉(zhuǎn)第二步, 直到被標號或標號過程無法進行下去, 則標號過程結(jié)束.</p><p>　　若被標號, 則存在一條可增廣鏈, 轉(zhuǎn)調(diào)整過程（第二步）; 若未被標號,則標號過程無法進行下去, 說明可行流就是最大流.</p&g

34、t;<p><b>　　3.2 調(diào)整過程</b></p><p>　　設是一條從到得增廣鏈, 的前向弧集合和后向弧集合分別用和表示, 設</p><p>　　如果上沒有后向弧, 則令取</p><p><b>　　第一步 令</b></p><p>　　第二步 去掉所有標號, 回到標

35、號過程, 對可行流重新標號.</p><p>　　上面所述的就是標號的全過程, 在計算時我們只用按照上面的步驟一步一步來, 就能得到一個網(wǎng)絡的最大流量.</p><p>　　3.3 標號算法的matlab實現(xiàn)</p><p>　　現(xiàn)有的最大流算法很多, 而對于最大流算法在實際中的應用問題, 大部分都是借助于計算機技術(shù)來評測算法的優(yōu)劣, 運行的時間越長, 說明算法的時

36、間復雜度越不好, 運行時間越短, 越精確, 說明算法越好. 下面就是標號算法在matlab上的實現(xiàn).</p><p>　　int n; C; % n為頂點數(shù), C為弧容量矩陣, 對于實際問題輸入數(shù)據(jù)</p><p>　　for(i=1:n)</p><p>　　for(j=1:n)</p><p><

37、b>　　f(i,j)=0;</b></p><p><b>　　end;</b></p><p>　　end %取初始可行流f為零流</p><p>　　for(i=1:n)</p><p>　　No(i)=0;d(i)=0;</p><p

38、>　　end %No, d記錄標號</p><p><b>　　while(1)</b></p><p>　　No(1)=n+1;d(1)=Inf; %給發(fā)點vs標號</p><p>　　while(1) pd=1; %標號過程</p>&

39、lt;p>　　for(i=1:n)</p><p>　　if(No(i)) %選擇一個已標號的點vi</p><p>　　for(j=1:n)</p><p>　　if(No(j)==0&f(i,j)<C(i,j)) %對于未給標號的點vj, 當vivj為非飽和弧時</p><p&g

40、t;　　No(j)=i; d(j)=C(i,j)-f(i,j); pd=0; </p><p>　　if(d(j)>d(i))</p><p>　　d(j)=d(i);</p><p><b>　　end</b></p><p>　　elseif(No(j)==0& f(j,i)>0) %對于

41、未給標號的點vj, 當vjvi為非零流弧時</p><p>　　No(j)=-i; d(j)=f(j,i); pd=0;</p><p>　　if(d(j)>d(i))</p><p>　　d(j)=d(i);end ;end; end; end; end</p><p>　　if(No(n)|pd)</p><p&

42、gt;　　break ; end; end %若收點vt得到標號或者無法標號, 終止標號過程</p><p><b>　　if(pd)</b></p><p>　　break;end %vt未得到標號, f已是最大流, 算法終止</p><p>　　dvt=d(n);t=n;

43、 %進入調(diào)整過程, dvt表示調(diào)整量</p><p><b>　　while(1)</b></p><p>　　if(No(t)>0)</p><p>　　f(No(t),t)=f(No(t),t)+dvt; %前向弧調(diào)整</p><p>　　elseif(No(t)<0)</

44、p><p>　　f(No(t),t)= f(No(t),t)-dvt;</p><p>　　end %后向弧調(diào)整</p><p>　　if(No(t)==1)</p><p>　　for(i=1:n)</p><p>　　No(i)=0; d(i)=0;</p>&

45、lt;p>　　end; break;end %當t的標號為vs時, 終止調(diào)整過程</p><p>　　t=No(t); end;end; %繼續(xù)調(diào)整前一段弧上的流f</p><p><b>　　wf=0;</b></p><p>　　for(j=1:n)</p><p&g

46、t;　　wf= wf+f(1,j); end %計算最大流量</p><p>　　f; %顯示最大流</p><p>　　wf %顯示最大流量</p><p>　　No %顯示標號, 由此可得最小割, 程序結(jié)

47、束</p><p>　　上面的算法標明了標號算法在matlab上的具體實現(xiàn), 對于一個實際問題, 則可以在第一步輸入數(shù)據(jù), 通過算法得到最大流和最小割等, 既簡潔, 又方便.</p><p>　　3.4標號法應用舉例</p><p>　　在現(xiàn)實生活中, 很多最優(yōu)化問題, 如通過求交通網(wǎng)絡上的最大流來安排貨物的運輸情況, 以達到合理利用道路流量等都需要對原有系統(tǒng)進行簡

48、化. 下面的兩個例子就是實際問題的簡化:</p><p>　　解: 先給發(fā)點標號. 檢查的鄰接點1, 2 , 發(fā)現(xiàn)1點滿足, 且那么給1點標號, 2點不滿足標號條件. 再檢查1的鄰接點2和3, 發(fā)現(xiàn)2滿足, 那么給2標號 3點不滿足標號條件. 再檢查2的鄰接點3和4, 4點滿足 且 那么給4點標號, 再看3點, 3點滿足 那么給3點標號, 再檢查3的鄰接點, 發(fā)現(xiàn)點滿足 那么給點標號, 點已經(jīng)得到了標號, 說明

49、存在增廣鏈, 標號過程結(jié)束. 如圖所示:</p><p><b>　　下面進入調(diào)整過程:</b></p><p>　　顯然: 是一條增廣鏈.</p><p><b>　　取 令</b></p><p>　　按照逆增廣鏈方向（即由）, 則有: 調(diào)整過程結(jié)束, 見下圖, 圖中粗線為調(diào)整后的增廣鏈.

50、</p><p>　　重新進入標號過程, 當對1點進行標號后, 標號工程無法進行下去, 點并未得到標號, 說明此時是最大流. 最大流的流量 同時得到一個最小割集, 得到下圖, 虛線為最小割集.</p><p>　　上述結(jié)果也可以直接用給定的程序運行一下, 進行對比, 只需給定:</p><p>　　; =[ ; ; 4 ; ;

51、 ; ]; 運行程序可以得到結(jié)果:</p><p>　　wf=; No= ; 將此結(jié)果和用標號過程的進行對比, 驗證結(jié)果的正確性.</p><p>　　只有一個發(fā)點和一個收點的網(wǎng)絡為簡單網(wǎng)絡. 但是實際上, 在實際應用問題上有多個發(fā)點和多個收點的網(wǎng)絡, 為了簡化計算, 我們可將它們轉(zhuǎn)化為簡單網(wǎng)絡, 這樣能使得計算效率大大提高. 轉(zhuǎn)化方法為虛擬一個發(fā)點（用表示發(fā)點集,

52、 表示收點集）, 對于每一個增加一條從到的弧, 適當定義該弧的容量, 從而將原網(wǎng)絡擴充為一個簡單的網(wǎng)絡. 下面的例題就是對一個實際問題的擴充的情況下求其最大流量.</p><p>　　例題: 某大型物流公司想要沿著如下圖的交通網(wǎng)絡從1和2點經(jīng)過中間運輸點3、4、5運往6和7兩點, 每條路段對該公司每天通過的物流量都有限制, 其值為圖中每條弧上的權(quán)數(shù), 現(xiàn)1和2點各有物資100和200噸, 而6和7點需求量各為15

53、0和180噸, 試問物流公司最多能通過這個交通網(wǎng)絡運送多少物資, 并給出運輸方案.</p><p>　　解: 通過問題的分析, 我們能發(fā)現(xiàn)上面所述問題就是求最大流量問題, 但是我們發(fā)現(xiàn)始點和收點都超過一個, 無法按照原來的方法計算, 所以我們要對原來網(wǎng)絡進行擴充.</p><p>　　我們按照上面的方法把原圖擴充為一個簡單網(wǎng)路, 如下圖:</p><p>　　設 其

54、為可行流, 給個點標號后如下圖: </p><p>　　在圖12中尋求一條增廣鏈 將修改成, 重新標號后得到圖3-4-8:</p><p>　　在圖13中尋求一條增廣鏈 將修改為, 并重新標號后得到圖3-4-9:</p><p>　　在圖14中尋求一條增廣鏈 將修改成, 并重新標號得到圖3-4-10:</p><p>　　在圖15中尋求一條增

55、廣鏈 將修改為, 并重新標號得到圖3-4-11:</p><p>　　在圖16中尋求一條增廣鏈 將修改為, 并重新標號得到圖3-4-12:</p><p>　　在圖17中尋求一條增廣鏈 將修改為, 并重新標號得到圖3-4-13:</p><p>　　此時, 我們可以發(fā)現(xiàn)不再存在增廣鏈, 點也得不到標號, 算法結(jié)束.</p><p>　　因此,

56、 為最大流, 最大流流量為 運輸方案為1運出100噸, 2運出200噸, 6點云錦60噸, 7點運進180噸. </p><p>　　上述兩個例子都是最大流算法在實際中的應用, 其實上面提到的只是生活中的一個方面, 最大流算法應用廣泛, 其更多的解法還需我們努力去發(fā)掘.</p><p>　　4 網(wǎng)絡最大流其他算法簡要介紹</p><p>　　上面提到的標號算法是現(xiàn)在

57、運籌學教科書中主要介紹的方法, 也是現(xiàn)在計算最大流量的重要算法, 來源于Ford和Fulkerson. 其他算法還包括預流推進算法、Edmonds – Karp算法、Dinic算法、SAP算法、最大容量路徑算法、Capacity Scaling Algorithm等, 它們各有其優(yōu)點, 復雜度也各有差異. 下面來簡要介紹一下這些算法:</p><p>　　Shortest Augmenting Path (SAP

58、)是每次尋找最短增廣路的一類算法, Edmonds - Karp 算法以及后來著名的Dinic算法都屬于此. SAP算法思想為: 在無權(quán)邊的有向圖中尋找最短路, 最簡單的方法就是廣度優(yōu)先搜索 (BFS), E-K算法就直接來源于此. 每次用一遍BFS尋找從源點到終點的最短路作為增廣路徑, 然后增廣流量并修改剩余網(wǎng)絡, 直到不存在新的增廣路徑. E-K算法的時間復雜度為 由于BFS要搜索全部小于最短距離的分支路徑之后才能找到終點因此可以想

59、象頻繁的BFS效率是比較低的. 實踐中此算法使用的機會較少.</p><p>　　Dinic算法：BFS尋找重點速度太慢, 而DFS又不能保證找到最短路徑. 1970年Dinic提出一種思想, 其結(jié)合了BFS與DFS的優(yōu)勢, 采用構(gòu)造分層網(wǎng)絡的方法可以較快找到最短增廣路, 此算法又稱為阻塞流算法（Blocking Flow Algorithm）.</p><p>　　首先定義分層網(wǎng)絡, 在

60、生于網(wǎng)絡中從起始進行BFS, 這樣每個頂點在BFS樹中會得到一個距源點的距離, 若 直接從出發(fā)可到達的點距離為1, 下一層距離為2……, 稱所有具有相同距離的頂點位于同一層, 在分層網(wǎng)絡中, 只保留滿足條件的邊, 這樣在分層網(wǎng)絡中的任意路徑就成為到達頂點的最短路徑. Dinic算法每一用一遍BFS構(gòu)建分層網(wǎng)絡, 然后在中一遍DFS找到所有到終點的路徑增廣; 之后重新構(gòu)造, 若終點不在中則算法結(jié)束. Dinic算法的時間復雜度為. 由于較

61、少的代碼量和不錯的運行效率, Dinic算法在實踐中比較常見.</p><p>　　Improved SAP算法：通常的SAP算法在尋找增廣路時總要先進行BFS, BFS最壞情況下復雜度為, 這樣使得普通SAP算法最壞情況下時間復雜度達到了. 為了避免這種情況, Ahuja和Orlin在1987年提出了Improved SAP算法, 它充分利用了距離標號的作用, 每次發(fā)現(xiàn)頂點無出弧時不是像Dinic算法那樣到最后

62、進行BFS, 而是就地對頂點距離重標號, 這樣相當于在遍歷的同時順便構(gòu)建了新的分層網(wǎng)絡, 每輪尋找之間不必再插入全圖的BFS操作, 極大提高了運行效率. 與Dinic算法不同, ISAP中的距離標號是每個頂點到達終點的距離,之后從源點開始, 進行如下三步操作: （1） 當前頂點為終點時增廣; （2） 當前頂點有滿足的出弧時前進; （3） 當前頂點無滿足條件的出弧時重標號并回退一步. 整個循環(huán)當源點的距離符號時結(jié)束. 雖然ISAP算法時間

63、復雜度與Dinic相同, 都是, 但在實際表現(xiàn)中要好很多. 要提的一點是關(guān)于ISAP的一個所謂GAP優(yōu)化. 由于從到得一條最短路徑的頂點距離標號單調(diào)遞減, 且相鄰頂點標號差嚴格等于1, 因此可以預見如果在當前網(wǎng)絡中距離標號為的頂</p><p>　　最大容量路徑算法：1972年E-K提出另外一種最大流算法. 即每次尋找增廣路時不找最短路徑, 而是尋找容量最大路徑.可以預見, 此方法與SAP算法相比可更快逼近最大流

64、, 從而降低增廣操作的次數(shù). 實際算法也很簡單, 只用把前面E-K算法的BFS部分替換為一個類Dijkstra算法即可. BFS是, 簡單Dijkstra時間復雜度為, 因此效果可想而知.</p><p>　　Capacity Scaling Algorithm：此算法在尋找增廣路時不必要局限于尋找最大容量, 而是只要找到一個可接受的較大值即可, 一方面有效降低尋找增廣路時的復雜度, 另一方面增廣操作次數(shù)也不會增

65、加太多. 時間復雜度為, 實際效率稍好于前面提到的E-K算法, 但是仍然不及Dinic和ISAP算法.</p><p>　　其實正如其他作者在論文中所提到的那樣, 實際中面對不同問題解決的方法可能不止一種, 甚至有很多解決的方法, 下面就是一個實際問題的縮影, 而且運用的不是傳統(tǒng)方法, 而是用一種新的算法得到它的最大流.</p><p>　　例2: 求圖4-1中的網(wǎng)絡最大流量.</p

66、><p><b>　　解:</b></p><p>　　如圖4-2所示, 找到了容量網(wǎng)絡中的極大一致鏈, 找到該鏈上各弧容量的最小值 記為. </p><p>　?。?）在極大一致鏈上的每條弧容量分別減去該最小值, 得到圖4-3的容量網(wǎng)絡:</p><p>　　同理, 得到 給弧上每條弧容量分別減去, 得到圖4-4:<

67、/p><p><b>　　同上方法得到下圖:</b></p><p>　　對圖4-6進行調(diào)整得到</p><p>　　計算結(jié)束, 此時得到容量網(wǎng)絡的最大流為: .</p><p>　　上面的算法稱為銷鏈算法, 與經(jīng)典的Ford-Fulkerson標號算法相比, 該算法避免了多次對網(wǎng)絡的標號過程, 大大降低了算法的復雜度. 這

68、里的極大一致鏈也使得算法得到了極大的優(yōu)化, 加快了整個算法的執(zhí)行速度, 上例的實例也驗證了算法的效率和實用性. </p><p><b>　　5 小結(jié)</b></p><p>　　本文重在對現(xiàn)有的一些求網(wǎng)絡最大流算法進行介紹, 以及對經(jīng)典算法進行了舉例. 當然, 最重要的還是能把這些算法應用在實際生活中. 我們知道, 一種算法的好壞取決于其精確度和復雜度, 現(xiàn)有的IS

69、AP算法無疑是所有算法里面差不多是最好的, 但是增廣路算法還是其基礎(chǔ), 我們要在很好理解增廣路算法的基礎(chǔ)上才能更好理解其他算法. 也只有很好理解傳統(tǒng)方法才能創(chuàng)造新算法. 本文介紹的算法可借助編譯程序計算出他們的復雜度, 然后將它們進行對比, 能發(fā)現(xiàn)各自的優(yōu)點. 如今, 網(wǎng)絡流問題在實際中應用越來越廣泛, 新的算法也在不斷出現(xiàn), 一些經(jīng)典的算法在過去幾十年間得到了很大的改進, 使得最大流問題的研究也越來越趨向成熟. 關(guān)鍵是在實際中我們能否

70、找到其和最大流問題的聯(lián)系, 否則會走很多彎路. 事實上, 很多應用問題所對應的最大流問題都有比較明顯的特征, 但充分利用特征, 設計面向應用問題的算法并不多. 隨著計算機技術(shù)的發(fā)展, 相信在不久的將來, 網(wǎng)絡最大流問題能得到更好的發(fā)展.</p><p><b>　　參考文獻</b></p><p>　　廖敏. 運籌學基礎(chǔ)與應用 [M]. 南京: 南京大學出版社, 20

71、09: 190-197.</p><p>　　弗雷德里克?S?希利爾, 杰拉爾德?J?利伯曼（胡運權(quán)等譯）. 運籌學導論 [M]. 北京:清華大學出版社, 2007 : 375-381.</p><p>　　L R Ford, D R Fulkerson. Maximum flow through a network. Canadian Journal of Math, 1956, 8(5

72、): 399-404.</p><p>　　王志強. 網(wǎng)絡最大流的新算法 [D]. 陜西: 寶雞文理學院, 2009. </p><p>　　張憲超, 陳國良, 萬穎瑜等. 網(wǎng)絡最大流問題研究進展 [J]. 計算機研究與發(fā)展學報, 2003, 40(9): 1281-1292.</p><p>　　A.V. Goldberg and R.E. Tarjan. A n

73、ew approach to the maximum-flow problem. Journal of the ACM, 1988, 35: 921-940.</p><p>　　趙可培. 運籌學 [M]. 第二版. 上海: 上海財經(jīng)出版社, 2008: 243-249.</p><p>　　R. K. Ahuja and J.B. Orlin. A fast and simple alg

74、orithm for the maximum flow problem. Oper. Res. 1989, 37: 748-759.</p><p>　　Maria Grazia Scutella. A note on the parametric maximum flow problem and some related reoptimization issues. Ann Oper Res, 2007, 15