基于最短增廣鏈的最大流改進(jìn)算法

趙禮峰，紀(jì)亞勁

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

基于最短增廣鏈的最大流改進(jìn)算法

趙禮峰，紀(jì)亞勁

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

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

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

0 引 言

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

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

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

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

1 基本概念

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

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

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

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

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

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

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

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

定義2：對(duì)于剩余網(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)稱(chēng)為G的關(guān)于f的分層剩余網(wǎng)絡(luò)[18]。

2 一種改進(jìn)的最大流算法

2.1 算法思想

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

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

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

證明：增廣鏈的定義是，對(duì)于G中一條(vs,vt)鏈P，若P的前向弧為f非飽和弧，后向弧為f正弧，則稱(chēng)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中的最短增廣鏈。而通過(guò)該算法修復(fù)的路徑仍是AG(f)中的(vs,vt)路徑，所以修復(fù)的路徑仍是最短增廣鏈。

2.2 算法步驟

最大流算法：

輸入：原容量網(wǎng)絡(luò)G=(V,A,c)與指定的發(fā)點(diǎn)vs、收點(diǎn)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)號(hà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對(duì)fk進(jìn)行增廣，相應(yīng)修改AG(fk)中P上弧的容量，刪去P上容量為零的弧和原網(wǎng)絡(luò)中相應(yīng)的弧。

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

2.3 算法可行性分析

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

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

設(shè)G的頂點(diǎn)數(shù)為n，弧數(shù)為m。因?yàn)樗惴ㄖ袠?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)中尋找增廣鏈后都要?jiǎng)h去至少一條弧，所以至多找m次(vs,vt)路，每次尋找(vs,vt)路的計(jì)算量為O(n)，于是得到算法的時(shí)間復(fù)雜度為：O(n+n·m+n·n·m)=O(n2m)。

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

3 實(shí)例分析

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

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

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

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

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

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

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

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

圖4 最大流f2

4 算法的仿真與分析

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

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

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

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

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

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

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

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

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

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

兩種算法的平均運(yùn)行時(shí)間對(duì)比曲線如圖5所示。

圖5 兩種算法的平均運(yùn)行時(shí)間

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

5 結(jié)束語(yǔ)

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

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

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

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

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

國(guó)家自然科學(xué)基金青年基金項(xiàng)目(61304169)

趙禮峰(1959-)，男，教授，碩士研究生導(dǎo)師，研究方向?yàn)閳D論及應(yīng)用、矩陣論；紀(jì)亞勁(1991-)，男，碩士研究生，研究方向?yàn)閳D論及其在通信中的應(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