沈玥名,趙承業(yè)

(1.中國(guó)計(jì)量大學(xué) 經(jīng)濟(jì)與管理學(xué)院,浙江 杭州 310018;2.中國(guó)計(jì)量大學(xué) 理學(xué)院,浙江 杭州 310018)

對(duì)最小生成樹(shù)的研究一直是圖論中的經(jīng)典內(nèi)容,它不僅涉及一系列豐富的理論問(wèn)題,最小生成樹(shù)模型還可以模擬建筑業(yè)、交通業(yè)和通訊產(chǎn)業(yè)的很多建設(shè)成本問(wèn)題[1]。在構(gòu)造最小生成樹(shù)算法中,在1956、1957年P(guān)rim算法[2]與Kruskal算法[3]分別被提出,這兩種算法都是在多項(xiàng)式時(shí)間內(nèi)運(yùn)行的貪婪算法。賀軍忠等[4]研究了這兩種算法在執(zhí)行過(guò)程、時(shí)間復(fù)雜度和實(shí)現(xiàn)方法等方面的不同點(diǎn)。隨后江波等[5]研究了Prim算法的改進(jìn)算法,使其能動(dòng)態(tài)調(diào)整自身的性能,適合于稠密圖與稀疏圖。除了單純的算法的研究,算法的具體應(yīng)用例如張寧寧[6]基于Kruscal算法最小樹(shù)原理改進(jìn)AP(Affinity Propagation)聚類算法完成生產(chǎn)性服務(wù)需求的聚類。

在網(wǎng)絡(luò)中尋找最小生成樹(shù)是否為最短路樹(shù)的判定算法,主要為了解決最小生成樹(shù)成本分?jǐn)倖?wèn)題。在此問(wèn)題中,我們關(guān)心最小生成樹(shù)得到的最小權(quán)重和如何在各個(gè)結(jié)點(diǎn)間進(jìn)行公平的分配問(wèn)題[1]。該問(wèn)題最早由Kleitman[7]于1973年提出。我們考慮下面的一個(gè)小例子[8],見(jiàn)圖1:有三個(gè)小區(qū)(三個(gè)代理)用1,2,3來(lái)表示。這些小區(qū)都需要用管道連接到自來(lái)水廠(源點(diǎn)0),代理們目標(biāo)就是自身支付的管道成本最小。經(jīng)過(guò)計(jì)算后,最小生成樹(shù)的總成本為α+β+γ,具體最小生成樹(shù)T如圖1,N={1,2,3},c01=α,c12=β,c23=γ。非常自然地想到1,2,3分配成本可以是φ1=α/3、φ2=α/3+β/2以及φ3=α/3+β/2+γ/3。我們把這種自然的分配方案稱為路徑邊分?jǐn)?。?dāng)最小生成樹(shù)中存在c03<α/3+β/2+γ/3時(shí),代理3將選擇直接連接到源頭,路徑邊分?jǐn)偩筒皇且粋€(gè)公平的分配規(guī)則。

如果對(duì)一個(gè)給定的網(wǎng)絡(luò),存在網(wǎng)絡(luò)的最小生成樹(shù)是從源點(diǎn)出發(fā)的該網(wǎng)絡(luò)的最短路樹(shù),就可以采用上面的分?jǐn)偡桨竵?lái)進(jìn)行成本分?jǐn)?。因?本文重點(diǎn)研究判定一個(gè)網(wǎng)絡(luò)是否存在這樣的最小生成樹(shù)的算法。

1 準(zhǔn)備工作

工作本文涉及的,本文涉及的,未經(jīng)說(shuō)明的概念或?qū)I(yè)術(shù)語(yǔ),圖和網(wǎng)絡(luò)領(lǐng)域的詳見(jiàn)文獻(xiàn)[9],算法領(lǐng)域的詳見(jiàn)文獻(xiàn)[10]。給定一個(gè)帶權(quán)重的有向網(wǎng)絡(luò)G=(V,E)和權(quán)重函數(shù)ω:E→R,該權(quán)重函數(shù)將每一條邊賦予一個(gè)實(shí)數(shù)值作為這條邊的權(quán)重。網(wǎng)絡(luò)中一條路徑p=的權(quán)重ω(p)是構(gòu)成該路徑的所有邊的權(quán)重之和:

定義從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑權(quán)重δ(u,v)如下:

從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑則定義為任何一條權(quán)重為ω(p)=δ(u,v)的從u到v的路徑p。單源最短路問(wèn)題:給定一個(gè)網(wǎng)絡(luò)G=(V,E),我們希望找到給定的源結(jié)點(diǎn)sV到每個(gè)結(jié)點(diǎn)vV的最短路徑。求解單源最短路的算法有Dijkstra算法、Bellman-Ford算法[10]。文獻(xiàn)[10]中也證明了Dijkstra算法的結(jié)果是一個(gè)以源結(jié)點(diǎn)為根結(jié)點(diǎn)的有根樹(shù),稱為最短路樹(shù)。與上面類似,給定一個(gè)帶權(quán)重的有向網(wǎng)絡(luò)G=(V,E)和權(quán)重函數(shù)ω:E→R,我們希望找到網(wǎng)絡(luò)G的一棵生成樹(shù),它的權(quán)重的值最小,這樣的樹(shù)稱為是網(wǎng)絡(luò)G的最小生成樹(shù)。從最短路樹(shù)的定義,我們知道最短路樹(shù)也是網(wǎng)絡(luò)的一個(gè)生成樹(shù),但不能保證一定是該網(wǎng)絡(luò)的最小生成樹(shù)。圖2的例子說(shuō)明了這一情況。

圖2 同一連通圖的單源最短路生成樹(shù)與最小生成樹(shù)Figure 2 Shortest path spanning tree and minimum cost spanning tree of the same connected graph

2 判定算法及分析

2.1 Dijkstra算法與Prim算法

我們首先給出判定算法的兩個(gè)基礎(chǔ)算法:Dijkstra算法和Prim算法。因?yàn)槲墨I(xiàn)[11]中給出的算法描述比較容易理解,我們下面采用文獻(xiàn)[11]中算法描述如下:

算法Dijkstra(G,s)

//單源最短路的Dijkstra算法

//輸入:網(wǎng)絡(luò)G=(V,E)和它的頂點(diǎn)s,其中E中邊的權(quán)重非負(fù)

//輸出:對(duì)于V中任意頂點(diǎn)v,從s到v的最短路徑長(zhǎng)度dv,

//以及路徑上倒數(shù)第二個(gè)頂點(diǎn)pv

1.Initialize(Q) //將頂點(diǎn)優(yōu)先隊(duì)列初始化為空

2.forV中每一個(gè)頂點(diǎn)vdo

3.dv←∞;pv←null

4.Insert(Q,v,dv) //初始化優(yōu)先隊(duì)列中頂點(diǎn)的優(yōu)先級(jí)

5.ds←0;Decrease(Q,s,ds) //將s的優(yōu)先級(jí)更新為ds

6.VT←Φ

7.fori←0to|V|-1do

8.u*←DeleteMin(Q) //刪除優(yōu)先級(jí)最小的元素

9.VT←VT∪{u*}

10.forV-VT中每一個(gè)和u*相鄰的頂點(diǎn)udo

11.ifdu*+w(u*,u)

12.du←du*+w(u*,u);pu←u*

13.Decrease(Q,u,du)

引理2.1[11]如果網(wǎng)絡(luò)由權(quán)重矩陣表示,優(yōu)先隊(duì)列用無(wú)序數(shù)組表示,則Dijkstra算法的復(fù)雜度為O(|V|2);若用鄰接表表示,優(yōu)先隊(duì)列用最小堆實(shí)現(xiàn),該算法復(fù)雜度為O(|E|log|V|)。

算法Prim(G)

//構(gòu)造最小生成樹(shù)的Prim算法

//輸入:網(wǎng)絡(luò)G=(V,E)

//輸出:ET,組成G的最小生E成樹(shù)的邊集

1.VT←{v0}

2.ET←Φ

3.fori←1to|V|-1do

4.在所有的邊(v,u)中,求權(quán)重最小的邊e*=(v*,u*),其中v在VT中,u在V-VT中

5.VT←VT∪{u*}

6.ET←ET∪{e*}

7.returnET

引理2.2[11]如果網(wǎng)絡(luò)由權(quán)重矩陣表示,優(yōu)先隊(duì)列用無(wú)序數(shù)組表示,則Prim算法的復(fù)雜度為O(|V|2);若用鄰接表表示,優(yōu)先隊(duì)列用最小堆實(shí)現(xiàn),該算法復(fù)雜度為O(|E|log|V|)。

2.2 判定算法

在Dijkstra算法和Prim算法的基礎(chǔ)上,將判定算法分為兩個(gè)階段:

第一階段,利用Dijkstra算法計(jì)算源點(diǎn)0到任意節(jié)點(diǎn)i的最短路權(quán)重,記為di,1≤i≤n;

第二階段,對(duì)構(gòu)造最小生成樹(shù)的Prim算法進(jìn)行修改,在每次增加權(quán)重最小邊時(shí),考慮新增頂點(diǎn)u*在ET中從u*到源點(diǎn)0的路徑權(quán)重和恰好為從源節(jié)點(diǎn)0到u*的最短路權(quán)重du*,如果存在這樣的最短路則繼續(xù)構(gòu)造,直到得到一個(gè)最小生成樹(shù)恰好就是單源最短路生成樹(shù);如果無(wú)論怎么構(gòu)造都不存在這樣的最短路,則說(shuō)明不存在這樣的最小生成樹(shù)。將這個(gè)修正算法稱為廣義的Prim算法簡(jiǎn)稱為GPrim算法,它用來(lái)判定是否存在一個(gè)最小生成樹(shù)是單源最短路生成樹(shù),具體算法如下:

算法GPrim(G,n)

//構(gòu)造最小生成樹(shù)的同時(shí)判定是否為單源最短路生成樹(shù)的廣義Prim算法

//輸入:網(wǎng)絡(luò)G=(V,E),n為網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)目

//輸出:True,如果存在最小生成樹(shù)為單源最短路生成樹(shù);否則,False

1.VT,ET,S←Φ//VT,ET,S為空棧

2.VT,.push(0) //源點(diǎn)0入頂點(diǎn)棧

3.S.push(NULL)

4.whileVT.length()

5.E*←Φ//E*為空棧

6.將所有權(quán)重最小的邊e*=(v*,u*),其中v在VT中,u在V-VT中入棧E*

7.whileS≠Φdo

8.flag ←0

9.whileE*≠Φdo

10.e*←E*.pop()

11.ifET中u*到源點(diǎn)0的路徑權(quán)值和≡du*do

12.VT.push(u*)

13.ET.push(e*)

14.S.push(E*)

15.flag ←1

16.break

17.ifflag=0do

18.ifS.peek()!=NULLdo

19.E*←S.pop()

20.else return False

21.whileE*=ΦandS.peek()!=NULLdo

22.VT.pop()

23.ET.pop()

24.E*←S.pop()

25.ifS.peek()=NULLreturnFalse //S棧頂元素為NULL

26.else

27.break

28.returnTrue

2.3 廣義Prim算法分析

定理2.1對(duì)于給定的網(wǎng)絡(luò),若判定算法給出True,則存在一個(gè)最小生成樹(shù)是以源點(diǎn)為根的單源最短路生成樹(shù);若判定算法給出False,則不存在這樣的最小生成樹(shù)。

證明GPrim算法在Prim算法基礎(chǔ)上,增加了判斷新增的頂點(diǎn),通過(guò)邊集ET到源點(diǎn)的權(quán)重是否恰好為它到源點(diǎn)的最短路權(quán)重。令Q=P∪{0}。若返回值為T(mén)rue,集合P每次增加一個(gè)頂點(diǎn),集合Q的導(dǎo)出子圖T增加一個(gè)頂點(diǎn)和一條邊,增加到N-1個(gè)頂點(diǎn)為止,此時(shí)得到的集合Q的導(dǎo)出子圖T正好是網(wǎng)絡(luò)的一棵生成樹(shù)。這棵生成樹(shù)恰好是該網(wǎng)絡(luò)的一個(gè)最小生成樹(shù),因?yàn)楦鶕?jù)Prim算法,從源點(diǎn)0開(kāi)始,每次增加一條和Q中頂點(diǎn)相鄰且權(quán)重最小的頂點(diǎn),因此我們得到了一棵網(wǎng)絡(luò)的最小生成樹(shù)。可知添加進(jìn)集合P中的新頂點(diǎn)top到源點(diǎn)0的最短路徑包含在導(dǎo)出子圖T中,因此T也是網(wǎng)絡(luò)的一個(gè)單源最短路生成樹(shù)。即該網(wǎng)絡(luò)存在一個(gè)最小生成樹(shù),它正好也是單源最短路生成樹(shù)。

若返回值為False,考慮算法找到所有與P中結(jié)點(diǎn)相鄰的結(jié)點(diǎn),構(gòu)成集合T;令d=min{ω(u,v):u∈P,v∈T},把所有到P中結(jié)點(diǎn)權(quán)重為d的T中結(jié)點(diǎn)按序號(hào)從大到小構(gòu)建E*;顯然,我們考慮了所有可能的最小生成樹(shù)構(gòu)造方法,如果不能找到滿足條件的新增頂點(diǎn),就說(shuō)明對(duì)任意的最小生成樹(shù),都不可能是單源最短路生成樹(shù)。

定理2.2判定算法的算法復(fù)雜度為O(|V|3)或O(|V|4)。

證明由引理2.1與2.2,我們知道最壞情形下,Dijkstra算法和Prim算法的復(fù)雜度都是O(|V|2)。因此判斷算法的復(fù)雜度主要由廣義Prim算法確定。

求所有權(quán)重最小的邊集,最大次數(shù)為i*(|V|-i),其中i是當(dāng)前已選結(jié)點(diǎn)集合VT的元素個(gè)數(shù)。顯然,循環(huán)whileE*≠Φ最大次數(shù)不超過(guò)網(wǎng)絡(luò)邊數(shù)|E|;循環(huán)whileS≠Φ最大次數(shù)不超過(guò)棧S的元素個(gè)數(shù),而|S|≤i;循環(huán)whileVT.length()

(|V|-1)(3|E|+|V|+1)。

當(dāng)|E|=O(|V|)時(shí),判定算法的時(shí)間復(fù)雜度是O(|V|3);當(dāng)|E|=O(|V|2)時(shí),判定算法的時(shí)間復(fù)雜度是O(|V|4)。

3 算例分析

利用Python語(yǔ)言和Networkx包實(shí)現(xiàn)了算法,基于真實(shí)社會(huì)網(wǎng)絡(luò)大多數(shù)是符合小世界網(wǎng)絡(luò)特征[12]。本文選擇利用Networkx包c(diǎn)onnected_watts_strogatz_graph(n,k,p)來(lái)生成測(cè)試網(wǎng)絡(luò)。其中n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),k為節(jié)點(diǎn)鄰居數(shù),p為隨機(jī)邊比例,i代表網(wǎng)絡(luò)任一節(jié)點(diǎn)。

圖3是一個(gè)隨機(jī)生成的n=20,k=3,p=0.3的小世界網(wǎng)絡(luò),圖4顯示它的滿足最短路條件的最小生成樹(shù)。表1給出網(wǎng)絡(luò)WS1的所有節(jié)點(diǎn)到源點(diǎn)0的最短路權(quán)重值。

表1 網(wǎng)絡(luò)WS1的所有節(jié)點(diǎn)到源點(diǎn)0的最短路權(quán)重值

圖3 隨機(jī)生成的小世界網(wǎng)絡(luò)WS1(n=20,k=3,p=0.3)Figure 3 Randomly generated small-world network WS1(n=20,k=3,p=0.3)

圖4 網(wǎng)絡(luò)WS1的最小生成樹(shù)(單源最短路生成樹(shù))Figure 4 Minimum spanning tree of WS1 network (Shortest path spanning tree)

使用Python語(yǔ)言隨機(jī)生成100個(gè),200個(gè),300個(gè),400個(gè),500個(gè)滿足條件n=20,k=3,p=0.3的小世界網(wǎng)絡(luò),統(tǒng)計(jì)存在最小生成樹(shù)是單源最短路生成樹(shù)的網(wǎng)絡(luò)個(gè)數(shù),結(jié)果見(jiàn)表2。

表2 隨機(jī)生成的小世界網(wǎng)絡(luò)(n=20,k=3,p=0.3) 最小生成樹(shù)是單源最短路生成樹(shù)個(gè)數(shù)

在此類網(wǎng)絡(luò)中,約有半數(shù)的網(wǎng)絡(luò)能夠找到這樣的最小生成樹(shù),同時(shí)也為單源最短路生成樹(shù)。

同時(shí)算法也考慮了實(shí)際運(yùn)行時(shí)間。此次實(shí)驗(yàn)運(yùn)行環(huán)境為:Intel(R) Xeon(R) CPU E3-1230v5@3.40 GHz 3.41 GHz,內(nèi)存16 GB,操作系統(tǒng)windows10,Python 3.6.4 32位,Networkx2.2。記錄了隨機(jī)生成滿足條件n=10,100,200,k=3,p=0.3的10個(gè)小世界網(wǎng)絡(luò)的運(yùn)行時(shí)間,重復(fù)5次,結(jié)果見(jiàn)表3。

表3 算法在節(jié)點(diǎn)數(shù)n=10,100,200的運(yùn)行時(shí)間

因?yàn)殡S機(jī)生成的小世界網(wǎng)絡(luò)的邊數(shù)和節(jié)點(diǎn)數(shù)具有線性關(guān)系,因此根據(jù)定理2.2,得到在該網(wǎng)絡(luò)上執(zhí)行的算法時(shí)間復(fù)雜度為O(|V|3),表3實(shí)際計(jì)算的數(shù)據(jù)也驗(yàn)證了這點(diǎn)。

3 結(jié) 論

本文給出了判斷任意網(wǎng)絡(luò)是否存在最小生成樹(shù)滿足最短路的條件的算法,從理論上證明了算法的有效性,并通過(guò)構(gòu)建隨機(jī)生成的小世界網(wǎng)絡(luò)驗(yàn)證了算法的可行性。

通過(guò)對(duì)算法時(shí)間復(fù)雜度的分析,和具體算例的計(jì)算時(shí)間分析,該算法因?yàn)閺?fù)雜度較高,因此當(dāng)網(wǎng)絡(luò)結(jié)點(diǎn)規(guī)模比較大,邊數(shù)稠密的情況下,需要比較長(zhǎng)的計(jì)算時(shí)間。于是,如何改進(jìn)算法,提高算法效率,是該問(wèn)題進(jìn)一步研究的方向。