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

趙禮峰，紀(jì)亞勁

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

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

趙禮峰，紀(jì)亞勁

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

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

最大流；分層剩余網(wǎng)絡(luò)；最短增廣鏈；BA無標(biāo)度網(wǎng)絡(luò)

0 引 言

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

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

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

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

1 基本概念

1.1 最大流的數(shù)學(xué)模型

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

網(wǎng)絡(luò)最大流模型:

1.2 分層剩余網(wǎng)絡(luò)

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

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

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

定義1：由V，A(f)和c(f)組成的網(wǎng)絡(luò)G(f)=(V,A(f),c(f))稱為網(wǎng)絡(luò)G關(guān)于f的剩余網(wǎng)絡(luò)。

定義2：對于剩余網(wǎng)絡(luò)G(f)=(V,A(f),c(f))，規(guī)定關(guān)于G(f)的子網(wǎng)絡(luò)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的關(guān)于f的分層剩余網(wǎng)絡(luò)[18]。

2 一種改進的最大流算法

2.1 算法思想

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

圖1 最短增廣鏈修復(fù)過程

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

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

由剩余網(wǎng)絡(luò)的定義知，剩余網(wǎng)絡(luò)中弧的容量為：

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

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

2.2 算法步驟

最大流算法：

輸入：原容量網(wǎng)絡(luò)G=(V,A,c)與指定的發(fā)點vs、收點vt；

輸出：最大流f。

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

Step2：先構(gòu)造剩余網(wǎng)絡(luò)G(fk)，再利用廣探法構(gòu)造分層剩余網(wǎng)絡(luò)AG(fk)，若AG(fk)中vt得不到標(biāo)號，結(jié)束，fk就是G的最大流，否則轉(zhuǎn)Step3。

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

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

Step5：對增廣鏈P進行修復(fù)，轉(zhuǎn)Step4，若不能修復(fù)，轉(zhuǎn)Step3。

2.3 算法可行性分析

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

2.4 算法復(fù)雜度分析

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

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

3 實例分析

例：求圖2中從vs到vt的網(wǎng)絡(luò)最大流。

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

(2)構(gòu)造剩余網(wǎng)絡(luò)G(f1)，然后利用廣探法構(gòu)造AG(f1)，見圖3。

圖2 容量網(wǎng)絡(luò)G

圖3 分層剩余網(wǎng)絡(luò)AG(f1)

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

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

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

圖4 最大流f2

4 算法的仿真與分析

為比較改進算法與最短增廣鏈算法的運行時間，分別在網(wǎng)絡(luò)規(guī)模為300,600,900,1 200,1 500,1 800個節(jié)點的BA無標(biāo)度網(wǎng)絡(luò)上進行仿真比較，編程環(huán)境為Matlab2012b。

BA無標(biāo)度網(wǎng)絡(luò)鄰接矩陣生成過程如下：

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

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

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

(4)計算節(jié)點度數(shù)累計概率并用賭輪法將新增節(jié)點與原有網(wǎng)絡(luò)節(jié)點連接并更新鄰接矩陣，直到達到給定的規(guī)模停止更新；

(5)將BA無標(biāo)度網(wǎng)絡(luò)鄰接矩陣中數(shù)值為1的元素替換為一定范圍內(nèi)的隨機數(shù)作為弧容量。

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

表1 兩種算法在不同規(guī)模網(wǎng)絡(luò)上的實驗結(jié)果

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

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

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

從圖5中更能明顯看出，改進算法的運行效率比最短增廣鏈算法高，并且節(jié)點數(shù)也多，優(yōu)化的效率更明顯。所以對于大型網(wǎng)絡(luò)新算法的適用性更強。

5 結(jié)束語

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

[1] 張憲超，陳國良，萬穎瑜.網(wǎng)絡(luò)最大流問題研究進展[J].計算機研究與發(fā)展，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，F(xiàn)ulkerson 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] 張憲超，陳國良.小容量網(wǎng)絡(luò)上的最大流算法[J].計算機研究與發(fā)展，2001,38(2)：194-198.

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

[12] 郭 強.無向網(wǎng)絡(luò)最大流問題研究[J].計算機工程與應(yīng)用，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] 趙禮峰，嚴子恒.基于增廣鏈修復(fù)的最大流求解算法[J].計算機應(yīng)用，2015,35(5)：1246-1249.

[18] 謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長沙:國防科技大學(xué)出版社，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 網(wǎng)絡(luò)出版時間：2017-07-05

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

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

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