基于最短增廣鏈的最大流改進算法

趙禮峰，紀亞勁

(南京郵電大學 理學院，江蘇 南京 210023)

基于最短增廣鏈的最大流改進算法

趙禮峰，紀亞勁

(南京郵電大學 理學院，江蘇 南京 210023)

網絡最大流是經典的組合優化問題，它的經典算法主要有三種，分別是Ford-Fulkerson算法、最短增廣鏈算法(Dinic算法)和預流推進算法。Ford-Fulkerson算法中由于增廣鏈的選取任意性而有時無法得到理想的最大流。最短增廣鏈算法在分層剩余網絡中尋找最短增廣鏈，從而避免了增廣鏈選取的任意性。但最短增廣鏈算法在求解最大流過程中每次增廣都需要重新尋找最短增廣鏈，利用率不高。針對這一問題，提出了一種修復最短增廣鏈的新算法。該算法在沿最短增廣鏈調整流量之后，刪除最短增廣鏈流量為零的弧，且尋找合適的路徑修復最短增廣鏈，從而提高了最短增廣鏈的使用效率，減少了最短增廣鏈的搜索次數。應用新算法進行了BA無標度網絡建模仿真。實驗結果表明，該算法運行效率要高于最短增廣鏈算法。

最大流；分層剩余網絡；最短增廣鏈；BA無標度網絡

0 引 言

網絡最大流問題是圖論中極其重要的分支，是經典的組合優化問題，也可以看成特殊的線性規劃問題[1]。它在運籌學、計算機、工程等眾多科學領域中有著廣泛的應用[2-3]，例如，運輸問題、分派問題、通信問題等都可以轉化為網絡最大流模型來解決。因此，研究網絡最大流算法具有很重要的意義。

至今為止，網絡最大流問題的研究已經有50多年的歷史，現已建立了較為完善的理論并且提出了一系列經典算法。如1956年提出的Ford-Fulkerson算法[4]，隨后Dinic,Edmonds和Karp對Ford-Fulkerson算法進行了改進，提出了最短增廣鏈算法[5-6]。該算法提出了分層剩余網絡的概念，其主要思想是每次都是沿著最短增廣鏈進行增廣。1986年，Karzanov提出了預留推進算法[7]，Goldberg和Tarjan對此進行了深入研究并提出了一系列的改進算法[8-9]；另外，還有大量的學者針對一些特殊網絡提出了自己的算法[10-16]，這些算法是如今研究大規模網絡的基礎。

Ford-Fulkerson算法的優點是適用度廣，但是每次都是任意尋找增廣鏈，使得算法復雜度偏高；最短增廣鏈算法在Ford-Fulkerson算法的基礎上改進很多，即沿著最短增廣鏈進行增廣，在很大程度上降低了復雜度。但是算法仍存在缺陷，由于每次沿最短增廣鏈增廣之后需重新尋找最短增廣鏈，所以利用率不高。

針對上述不足，提出了一種新的改進的最短增廣鏈算法。該算法通過一種方法來修復最短增廣鏈[17]，避免了反復重新尋找新的最短增廣鏈，以提高算法效率。

1 基本概念

1.1 最大流的數學模型

給定一個容量網絡G=(V,A,c)，其中V是頂點集，A是弧集，c是弧的容量，f(a)(a∈A)稱為通過弧a的流量。在網絡G中定義兩個頂點vs和vt，vs為G的發點，vt為G的收點。

網絡最大流模型:

1.2 分層剩余網絡

對于一個容量網絡G=(V,A,c)及G上的可行流f，令

稱A+(f)為前向弧集，A-(f)為后向弧集，且記A+(f)∪A-(f)=A(f)，令

稱cij(f)為弧(vi,vj)關于f的剩余容量。

定義1：由V，A(f)和c(f)組成的網絡G(f)=(V,A(f),c(f))稱為網絡G關于f的剩余網絡。

定義2：對于剩余網絡G(f)=(V,A(f),c(f))，規定關于G(f)的子網絡AG(f)=(V'(f),A'(f),c(f))，如下：

V'(f)={vt}∪{vi∈V|h(vi)

A'(f)={(vi,vj)∈A(f)|h(vj)=h(vi)+1

則AG(f)稱為G的關于f的分層剩余網絡[18]。

2 一種改進的最大流算法

2.1 算法思想

首先從容量網絡D的任一個可行流f1(例如零流)開始，構造G的關于f1的分層剩余網絡AG(f1)，在AG(f1)中使用深度優先搜索算法選取一條(vs,vt)路徑P1，沿P1對f1進行增廣，并相應修改P1上的容量，在AG(f1)中刪去P1上容量為零的弧，且同時在原網絡中刪去相應的弧，然后對P1進行修復，修復的方法是:從發點vs和收點vt出發，沿P1向中間逐點遍歷，若遇斷點便停止遍歷并分別記為斷點vi和vj，考察在AG(f1)中是否存在從vi到vj的路徑，若存在，則修復最短增廣鏈P1，繼續沿P1對f1進行增廣，直至不能修復，如圖1所示。之后在AG(f1)中重新選取增廣鏈P2，重復上述操作。經過有限次增廣，使得余下網絡不再有(vs,vt)路徑，從而得到新的可行流f2。vt在G(f2)中的層數大于vt在G(f1)中的層數，重新構造分層剩余網絡AG(f2)，對于AG(f2)重復以上的做法，得到可行流f3，一直做下去，直到得到可行流fk，使得G(fk)中不存在(vs,vt)路徑，此時fk即為G的最大流。

圖1 最短增廣鏈修復過程

定理1：分層剩余網絡AG(f)中(vs,vt)路就是容量網絡G中關于f的最短增廣鏈。若沿著最短增廣鏈增廣后，通過該方法修復的路徑仍為最短增廣鏈。

證明：增廣鏈的定義是，對于G中一條(vs,vt)鏈P，若P的前向弧為f非飽和弧，后向弧為f正弧，則稱P為關于f的(vs,vt)的增廣鏈。

由剩余網絡的定義知，剩余網絡中弧的容量為：

設P是剩余網絡G(f)中的一條(vs,vt)路，則P中任一條弧都滿足增廣鏈的定義。

又根據分層的規則易知，G(f)中任何最短(vs,vt)路都在AG(f)中，且AG(f)中任何(vs,vt)路都是G(f)的最短(vs,vt)路，即AG(f)中任何(vs,vt)路都是容量網絡G中的最短增廣鏈。而通過該算法修復的路徑仍是AG(f)中的(vs,vt)路徑，所以修復的路徑仍是最短增廣鏈。

2.2 算法步驟

最大流算法：

輸入：原容量網絡G=(V,A,c)與指定的發點vs、收點vt；

輸出：最大流f。

Step1：在G中取初始可行流f1(可以取零流)，令k=1。

Step2：先構造剩余網絡G(fk)，再利用廣探法構造分層剩余網絡AG(fk)，若AG(fk)中vt得不到標號，結束，fk就是G的最大流，否則轉Step3。

Step3：在AG(fk)中尋找(vs,vt)路P(深度優先原則)，轉Step4，若不存在，則令fk+1=fk,k=k+1，轉Step2。

Step4：沿P對fk進行增廣，相應修改AG(fk)中P上弧的容量，刪去P上容量為零的弧和原網絡中相應的弧。

Step5：對增廣鏈P進行修復，轉Step4，若不能修復，轉Step3。

2.3 算法可行性分析

該算法運行時，每次在分層剩余網絡中找到或修復一條最短增廣鏈后，都從發點vs出發沿不飽和弧進行增廣，一直推進到收點vt，增廣后最短增廣鏈上至少有一條飽和弧。設網絡G=(V,A,c)中共有m條弧，那么該算法最多經過m次增廣后，網絡G飽和，此時網絡G無法找到或修復一條最短增廣鏈，算法終止，得到網絡最大流。所以該算法會在有限的步驟之后終止。

2.4 算法復雜度分析

設G的頂點數為n，弧數為m。因為算法中構造的分層剩余網絡AG(fk)的層數隨著k單調增加，所以Step2中構造分層剩余網絡AG(fk)最多執行n-1次，又由廣探法知，每次構造分層剩余網絡AG(fk)的復雜度為O(m)。在AG(fk)中尋找增廣鏈后都要刪去至少一條弧，所以至多找m次(vs,vt)路，每次尋找(vs,vt)路的計算量為O(n)，于是得到算法的時間復雜度為：O(n+n·m+n·n·m)=O(n2m)。

在改進算法運行過程中，Step5中每一次對最短增廣鏈進行修復，就減少了在AG(fk)中最短增廣鏈的搜索次數，最終降低了時間復雜度。

3 實例分析

例：求圖2中從vs到vt的網絡最大流。

解:(1)對于網絡G，取零流f1作為初始可行流，令k=1。

(2)構造剩余網絡G(f1)，然后利用廣探法構造AG(f1)，見圖3。

圖2 容量網絡G

圖3 分層剩余網絡AG(f1)

(3)在AG(f1)選取最短增廣鏈P1=vsv1v2v3vt，δ=min{5,1,1,6}=1，沿P1對f1進行增廣流值1，得到新的可行流仍記為f1，修改AG(f1)，刪去AG(f1)和原網絡中的弧(v1,v2),(v2,v3)。

(4)對最短增廣鏈P1進行修復，斷點為v1,v3，修復后的最短增廣鏈為P1=vsv1v5v3vt，δ=min{4,6,3,5}=3，沿P1對f1進行增廣，流值為3，得到的可行流仍記為f1，修改AG(f1)，刪去AG(f1)和原網絡中的弧(v5,v3)。

(5)對于最短增廣鏈P1=vsv1v5v3vt不能修復，則轉到步驟(3)重新尋找最短增廣鏈，并且在之后的步驟中不需要進行修復，所以之后的算法執行情況和最短增廣鏈算法相同。最后得到容量網絡G的最大流f2，且最大流流值為v(f2)=9，見圖4。

圖4 最大流f2

4 算法的仿真與分析

為比較改進算法與最短增廣鏈算法的運行時間，分別在網絡規模為300,600,900,1 200,1 500,1 800個節點的BA無標度網絡上進行仿真比較，編程環境為Matlab2012b。

BA無標度網絡鄰接矩陣生成過程如下：

(1)先使用p=0.5的概率生成一個規模為50×50的完全隨機網絡，并用0表示對應的弧不存在，1表示對應的弧存在；

(2)求出鄰接矩陣的行和作為每個節點的度數；

(3)新增節點，并且給每個新增的節點生成50條邊；

(4)計算節點度數累計概率并用賭輪法將新增節點與原有網絡節點連接并更新鄰接矩陣，直到達到給定的規模停止更新；

(5)將BA無標度網絡鄰接矩陣中數值為1的元素替換為一定范圍內的隨機數作為弧容量。

對于每種規模，進行5次仿真實驗，然后取平均運行時間進行比較，結果見表1。

表1 兩種算法在不同規模網絡上的實驗結果

從表1中可以看出，改進算法和最短增廣鏈算法同樣都能精確地求出網絡最大流，并且改進算法的運行速度比最短增廣鏈算法快。

兩種算法的平均運行時間對比曲線如圖5所示。

圖5 兩種算法的平均運行時間

從圖5中更能明顯看出，改進算法的運行效率比最短增廣鏈算法高，并且節點數也多，優化的效率更明顯。所以對于大型網絡新算法的適用性更強。

5 結束語

網絡最大流在眾多領域中應用廣泛，而最短增廣鏈算法是求解網絡最大流問題的經典算法之一。與Ford-Fulkerson算法相比，其避免了增廣鏈選取的任意性，從而減少了算法復雜度。但最短增廣鏈算法在求解最大流的過程中，每條最短增廣鏈只能增廣一次，效率較低。文中提出的改進算法通過修復最短增廣鏈提高了最短增廣鏈的使用效率。仿真結果表明，該算法與其他最短增廣鏈算法相比，在不同規模的隨機網絡中運行速度都較快，因此求解網絡最大流的效率更高。

[1] 張憲超，陳國良，萬穎瑜.網絡最大流問題研究進展[J].計算機研究與發展，2003,40(9)：1281-1292.

[2] Pardalos P M,Resende M G C.Handbook of applied optimization[M].New York:Oxford University Press,2002:363-374.

[3] Schrijver A.On the history of the transportation and maximum flow problems[J].Mathematical Programming,2002,91(3):437-445.

[4] Ford J L R，Fulkerson D R．Maximum flow through a network[J].Canadian Journal of Mathematics，1956，8(5):399-404.

[5] Edmonds J，Karp R M．Theoretical improvements in algorithmic efficiency for networks flow problems[J]．Journal of ACM，1972，19(2):248-264.

[6] Dinic E A． Algorithm for solution of a problem of maximum flow in a network with power estimation[J]．Soviet Mathematics Doklady，1970，2(5):1277-1280.

[7] Karzanov A V．Determining the maximum flow in a network by the method of pre-flows[J]．Soviet Mathematics Doklady，1974，15(3):434-437.

[8] Goldberg A V.The partial augment-relabel algorithm for the maximum flow problem[C]//European symposium on algorithms.Berlin:Springer,2008:466-477.

[9] Goldberg A V，Rao S．Beyond the flow decomposition barrier[J]．Journal of ACM，1998，45(5):783-797.

[10] 張憲超，陳國良.小容量網絡上的最大流算法[J].計算機研究與發展，2001,38(2)：194-198.

[11] 邱偉星，王以凡，沈金龍.一個求無向網絡最大流的算法[J].南京郵電學院學報,1997，17(4)：170-172.

[12] 郭 強.無向網絡最大流問題研究[J].計算機工程與應用，2005,41(9)：76-78.

[13] Weihe K．Maximum (s，t)-flows in planar networks in O(|V|log|V|)-time[J]．Journal of Computer System Science，1997，55(3):454-476.

[14] Borradaile G，Klein P．An O(nlogn) algorithm for maximum st-flow in a directed planar graph[J]．Journal of ACM，2009，56(2):524-533.

[15] Negruseri C S，Pasoi M B，Stanley B，et al．Solving maximum flow problems on real world bipartite graphs[J]．Journal of Experimental Algorithmics，2011，16(3):14-28.

[16] Erickson J.Maximum flows and parametric shortest paths in planar graphs[C]//ACM-SIAM symposium on discrete algorithms.Austin,Texas,USA:ACM,2010:794-804.

[17] 趙禮峰，嚴子恒.基于增廣鏈修復的最大流求解算法[J].計算機應用，2015,35(5)：1246-1249.

[18] 謝 政.網絡算法與復雜性理論[M].長沙:國防科技大學出版社，2003.

Improved Algorithm of Maximum Flow with Shortest Augmenting Chain

ZHAO Li-feng，JI Ya-jin

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

The maximum network flow is a classic combinatorial optimization problem,which mainly consists of Ford-Fulkerson algorithm,the shortest augmenting chain algorithm (Dinic algorithm) and preflow push algorithm.The desired maximum flow from Ford-Fulkerson algorithm could not be acquired because of the arbitrariness when choosing the augmented chain.The shortest augmenting chain algorithm can find the shortest augmenting chain in the remaining layered network to avoid the augmented chain selected arbitrary,however,it needs to search again shortest augmenting chain in maximum flow when augmenting with low using rate.Aimed at this problem,a new shortest augmenting chain repair algorithm is presented.After it has adjusted flow along the shortest augmenting chain the arc of zero flow on the augmented chain has been removed to retain the arc that the flow zero,which select the appropriate nodes to repair shortest augmenting chain in the remaining nodes for improving the efficiency and reducing the times of search shortest augmenting chain.The improved algorithm is verified through the modeling and simulation experimental in BA scale-free network,which shows that its efficiency is higher than the shortest augmenting chain algorithm.

maximum flow;remaining layered network;shortest augmenting chain;BA scale-free network

2016-08-18

2016-11-23 網絡出版時間：2017-07-05

國家自然科學基金青年基金項目(61304169)

趙禮峰(1959-)，男，教授，碩士研究生導師，研究方向為圖論及應用、矩陣論；紀亞勁(1991-)，男，碩士研究生，研究方向為圖論及其在通信中的應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1650.040.html

TP301.6

A

1673-629X(2017)08-0088-04

10.3969/j.issn.1673-629X.2017.08.018