基于分層圖的最短路徑選擇問(wèn)題研究

王鈞盛,雷欣祺,房慧宇,孔揚(yáng)濤

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,廣西 南寧 530004)

0 引言

路徑選擇問(wèn)題是圖論中的一個(gè)經(jīng)典問(wèn)題,其在城市建設(shè)、資源調(diào)用、路線規(guī)劃等方面有著很重要的應(yīng)用。求解2個(gè)端點(diǎn)之間的最短距離是路線選擇問(wèn)題中最重要的應(yīng)用之一,現(xiàn)存在如下情況:n個(gè)頂點(diǎn)之間有m條帶權(quán)有向邊相連,求從某個(gè)源點(diǎn)到某個(gè)目標(biāo)點(diǎn)的最短距離。在這種無(wú)限制條件的情況下求解該問(wèn)題,可以使用諸如Dijkstra等單源最短路徑算法來(lái)求解[1]。然而,當(dāng)存在限制條件時(shí),則必須對(duì)傳統(tǒng)算法進(jìn)行優(yōu)化,考慮現(xiàn)在存在如下限制條件:在m條帶權(quán)有向邊之中可以選擇k條邊使其權(quán)值歸0。在該條件下,求解一種選擇使得從源點(diǎn)到目標(biāo)點(diǎn)之間的最短距離最小。傳統(tǒng)的“枚舉+最短路徑算法”在處理本問(wèn)題時(shí)時(shí)間復(fù)雜度過(guò)高、效率太低。故本文提出利用分層圖來(lái)解決此類(lèi)問(wèn)題的算法。在本約束條件下,該問(wèn)題的求解具有很廣闊的現(xiàn)實(shí)應(yīng)用場(chǎng)景,如規(guī)劃出行優(yōu)惠路線、礦物開(kāi)采路線等[1]。

1 相關(guān)定義

1.1 圖

一個(gè)由n個(gè)頂點(diǎn)和m條帶權(quán)有向邊組成的圖G(V,E)中,V代表圖G的頂點(diǎn)集,E代表圖G的邊集,若2個(gè)頂點(diǎn)x,y之間存在一條帶權(quán)有向邊,則利用鄰接鏈表連接這2個(gè)頂點(diǎn)、建立該邊,并用w表示這條邊的權(quán)值,設(shè)初始源點(diǎn)為s,目標(biāo)點(diǎn)為t。

1.2 最短路徑

對(duì)圖G中的任意頂點(diǎn)對(duì)(u,v),如果從u出發(fā)只通過(guò)圖G中的邊,到達(dá)v的路徑長(zhǎng)度最小,則稱(chēng)這條路徑為從u到v的最短路徑[2],設(shè)disij為當(dāng)前從頂點(diǎn)i到頂點(diǎn)j的最短距離。

2 傳統(tǒng)算法

2.1 算法執(zhí)行過(guò)程

現(xiàn)在已有的傳統(tǒng)算法采用了“枚舉+最短路徑算法”的實(shí)現(xiàn)方式,在該算法下,只利用n個(gè)頂點(diǎn)以及m條邊建立一層圖,并不會(huì)考慮可以選擇k條邊的條件。本算法在建立好圖后,使用遞歸來(lái)確定選擇哪k條邊,將這k條邊的權(quán)值設(shè)置為0,在每一次枚舉情況中使用Dijkstra算法求解當(dāng)前源點(diǎn)s到目標(biāo)點(diǎn)t的最短路徑,并記錄下來(lái),當(dāng)枚舉完所有選擇情況后,取得的最小的disst即是該問(wèn)題的最優(yōu)解。

2.2 堆優(yōu)化的Dijkstra算法

求解最短路徑時(shí)使用堆來(lái)優(yōu)化Dijkstra算法,可以使得算法的效率更高。堆優(yōu)化的Dijkstra算法執(zhí)行流程如下[3]:

(1)輸入:圖G(V, E)、源點(diǎn)s。

(2)初始化:

距離數(shù)組dist[],對(duì)所有點(diǎn)初始化為正無(wú)窮大,dist[s]=0。

未處理點(diǎn)集S包含所有節(jié)點(diǎn)。

小頂堆heap。

(3)將源點(diǎn)s加入堆heap。

(4)while堆不空時(shí)。

從堆中取出距離源點(diǎn)最短的節(jié)點(diǎn)u,即dist[u]。

從未處理點(diǎn)集S中刪除u。

對(duì)每個(gè)與u相鄰的節(jié)點(diǎn)vinG.Adj[u] do。

如果dist[v]>dist[u]+w(u,v)。

更新dist[v]=dist[u]+w(u,v);

如果v在堆中,更新v的優(yōu)先級(jí)。

否則,將v加入堆。

(5)當(dāng)堆為空,算法結(jié)束。

此時(shí),對(duì)所有節(jié)點(diǎn)v,dist[v]存儲(chǔ)的是從源點(diǎn)s到v的最短距離。

關(guān)鍵步驟:(1)使用堆優(yōu)先處理距離源點(diǎn)短的節(jié)點(diǎn)。(2)重復(fù)更新目標(biāo)節(jié)點(diǎn)的距離值和堆中的優(yōu)先級(jí)。(3)結(jié)束條件是未處理點(diǎn)集為空,即所有節(jié)點(diǎn)都被處理過(guò)了。(4)經(jīng)過(guò)堆優(yōu)化后的Dijkstra算法用小頂堆來(lái)替代直接搜索,每次可以在O(logV)時(shí)間復(fù)雜度下取出dist[]最小點(diǎn),只需取V次最小點(diǎn)即可得到正確結(jié)果,故執(zhí)行一次堆優(yōu)化后的Dijkstra算法的時(shí)間復(fù)雜度為O(V×logV),效率更高。

2.3 枚舉算法

從m條邊中選擇k條邊可以使用遞歸搜索的枚舉算法來(lái)實(shí)現(xiàn),將該問(wèn)題抽象成為在有序數(shù)列1,……,n中選擇r個(gè)數(shù)字,處理1個(gè)數(shù)字時(shí)有2種情況:選或不選,如選擇當(dāng)前處理的數(shù)字,接下來(lái)問(wèn)題便改變?yōu)樵谑Ｓ嗟?,……,n-1序列中選擇r-1個(gè)數(shù)字,否則問(wèn)題則會(huì)改變?yōu)樵谑Ｓ?,……,n-1序列中再選擇r個(gè)數(shù)字,該算法的具體實(shí)現(xiàn)方法如下:

1 int A [number] ;2 #從1,…,n序列中還要選擇r個(gè)數(shù)字,當(dāng)前已選q個(gè)數(shù)字3 void Select (int n , int r , int q) {4 #如果序列剩余數(shù)字n小于還要選的數(shù)字的個(gè)數(shù)r,則證明出現(xiàn)異常5 if (n從1,…,n-1序列中選擇r-1個(gè)數(shù)字11 Select (n-1,r-1,q+1) ;12 #未選擇n這個(gè)數(shù)字—>從1,…,n-1序列中選擇r個(gè)數(shù)字13 Select(n-1,r,q) ;14 }15 }

2.4 時(shí)間復(fù)雜度分析

而對(duì)于每次的枚舉結(jié)果,均要執(zhí)行一次Dijkstra算法,執(zhí)行一次經(jīng)過(guò)堆優(yōu)化的Dijkstra算法的時(shí)間復(fù)雜度為O(V×logV)。

3 分層圖最短路算法

3.1 分層圖

分層圖是一類(lèi)特殊的有向圖,其特征是:(1)頂點(diǎn)集被分成多個(gè)層次集合,每一層次集合中的頂點(diǎn)稱(chēng)為一個(gè)層次。(2)在分層圖中僅允許存在從較低層次指向較高層次的邊。即如果存在一條從頂點(diǎn)u到頂點(diǎn)v的邊,則頂點(diǎn)u必須在頂點(diǎn)v的較低層次。(3)每個(gè)頂點(diǎn)只能屬于某一層次,不允許在多個(gè)層次中。

3.2 數(shù)學(xué)建模

利用分層圖的思想[4]對(duì)本問(wèn)題進(jìn)行數(shù)學(xué)建模,考慮原始圖G(V,E)的拓展,其中圖G含有n個(gè)頂點(diǎn)以及m條帶權(quán)有向邊。對(duì)于圖G的每一個(gè)頂點(diǎn)i,將其拓展為k+1個(gè)頂點(diǎn)i0,i1,i2,…,ik,即圖G被拓展為了k+1層圖。將未拓展前的圖視為第0層圖,設(shè)原圖中某頂點(diǎn)的下標(biāo)為x,則在拓展后第q層該頂點(diǎn)對(duì)應(yīng)的頂點(diǎn)下標(biāo)為q×n+x,每一層頂點(diǎn)之間的連接方式與第0層圖頂點(diǎn)之間的連接情況相一致,且該邊的權(quán)值等于其在0層圖對(duì)應(yīng)邊的權(quán)值,若第q層存在一條有向邊,權(quán)值為w,且q,令其權(quán)值為0。

例如:設(shè)當(dāng)前有n=5個(gè)頂點(diǎn),m=5條帶權(quán)有向邊,且k=2,則按照上述規(guī)則進(jìn)行數(shù)學(xué)建模后的新圖如圖1所示。

圖1 分層圖建模示例

3.3 算法執(zhí)行過(guò)程

首先按照上文的建模方法建立好圖,設(shè)源點(diǎn)為s,目標(biāo)點(diǎn)為t,則從源點(diǎn)s開(kāi)始,利用Dijkstra算法求源點(diǎn)到點(diǎn)t+k×n的最短路徑,該路徑長(zhǎng)度即為所有選擇情況下的最優(yōu)解,算法具體執(zhí)行過(guò)程如下[5]。

(1)輸入:一個(gè)分層圖G(V,E),源點(diǎn)s,目標(biāo)點(diǎn)t

(2)將圖G中的頂點(diǎn)集V按層次分組,形成多個(gè)層次Li(i=1,2,3,…)。

(3)初始化:

距離數(shù)組dist[],將源點(diǎn)到全部點(diǎn)的距離初始化為正無(wú)窮大。

dist[s]=0。

當(dāng)前層次號(hào)k=0。

(4)對(duì)當(dāng)前層次Lk執(zhí)行單源最短路徑算法,如Dijkstra算法:

取Lk中的每個(gè)節(jié)點(diǎn)u。

計(jì)算u到其他Lk中節(jié)點(diǎn)v的最短距離。

更新dist[v]的值。

(5)將下一層Lk+1中的節(jié)點(diǎn)加入未處理隊(duì)列。

如果Lk中的節(jié)點(diǎn)u到Lk+1節(jié)點(diǎn)v有邊,則dist[v]=dist[u]+w(u,v)。

否則dist[v]保持為正無(wú)窮大。

(6)k=k+1,處理下一層次Lk。

重復(fù)執(zhí)行4—5步,直到處理完最后一層次。

(7)輸出結(jié)果:

如果目標(biāo)點(diǎn)t在最后一層,輸出dist[t]。

否則輸出正無(wú)窮大,表示無(wú)路徑可達(dá)。

3.4 算法正確性分析

由于可以選擇k條邊將其權(quán)值歸零,利用分層圖的特性,將分層圖中的每一層當(dāng)作一種狀態(tài),第i層圖表示當(dāng)前k條邊中已經(jīng)選擇了i條。故在執(zhí)行Dijkstra算法處理第k+1層頂點(diǎn)時(shí),表示當(dāng)前已經(jīng)選擇了k條邊,令其權(quán)值歸0。而分層圖有明確的層次結(jié)構(gòu),每一層內(nèi)的節(jié)點(diǎn)只能與下一層節(jié)點(diǎn)相連,這一特點(diǎn)決定了算法可以采用按層次遞推的方式來(lái)求解最短路徑。

在算法開(kāi)始時(shí),正確初始化了源點(diǎn)s到各頂點(diǎn)的距離值,并對(duì)每一層進(jìn)行單源最短路徑的計(jì)算。由于前一層結(jié)果已經(jīng)是正確的,所以當(dāng)前層內(nèi)通過(guò)前一層頂點(diǎn)可達(dá)的邊也一定是最短的,這時(shí)更新的距離值也必定不大于真實(shí)最短距離。

在計(jì)算當(dāng)前層結(jié)束后,算法利用本層結(jié)果來(lái)推斷下一層頂點(diǎn)的最短距離下界。若當(dāng)前頂點(diǎn)通過(guò)前一層某頂點(diǎn)可達(dá),則下界就是該路徑長(zhǎng)度;否則下界為正無(wú)窮大。

通過(guò)每一層的遞推計(jì)算,隨著層數(shù)的增加,算法會(huì)在選擇與層次對(duì)應(yīng)的邊數(shù)的情況下逐步逼近源點(diǎn)到各頂點(diǎn)的真實(shí)最短距離。最后一層包含目標(biāo)點(diǎn)t的對(duì)應(yīng)頂點(diǎn)t+k×n時(shí),算法得到的dist[t+k×n]值即為源點(diǎn)到目標(biāo)點(diǎn)t的真實(shí)最短距離disst。

因此,該算法充分利用了分層圖的結(jié)構(gòu)特點(diǎn),按層次單調(diào)不減地更新距離值,可以確保最后輸出的結(jié)果一定是源點(diǎn)到目標(biāo)點(diǎn)的真實(shí)最短距離,故算法是正確的。

3.5 時(shí)間復(fù)雜度分析

算法在擴(kuò)展完圖G后,僅執(zhí)行1次最短路徑算法即可得到正確的答案,且Dijkstra算法執(zhí)行的時(shí)間復(fù)雜度僅和頂點(diǎn)數(shù)V有關(guān),擴(kuò)展后的圖共含有V×(k+1)個(gè)頂點(diǎn),故執(zhí)行一次堆優(yōu)化后的Dijkstra算法的時(shí)間復(fù)雜度為O(V×k×log(V×k)),擴(kuò)展圖所用的時(shí)間復(fù)雜度為O(V×k),故分層圖最短路算法的時(shí)間復(fù)雜度為O(V×k×log(V×k))。

4 比較測(cè)試

4.1 算法比較

分層圖最短路算法本質(zhì)上是一種以“空間換時(shí)間”為策略的算法,其時(shí)間復(fù)雜度O(V×k×log(V×k))僅和頂點(diǎn)數(shù)以及待選邊數(shù)有關(guān),與邊數(shù)m無(wú)關(guān),其中待選邊數(shù)k≤總邊數(shù)m,在k比較小的情況下效率更高。該算法對(duì)于存儲(chǔ)空間的要求很高,尤其是當(dāng)k的數(shù)據(jù)規(guī)模較大時(shí),算法需要分配很大的空間去擴(kuò)展圖。

綜上所述,分層圖最短路算法時(shí)間效率上遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)算法,但在存儲(chǔ)空間需求上,分層圖最短路算法要求的存儲(chǔ)空間會(huì)比傳統(tǒng)算法高。

4.2 實(shí)驗(yàn)測(cè)試

實(shí)驗(yàn)平臺(tái)選用Intel(R) Core(TM) i5-4590 CPU 3.30 GHz、內(nèi)存4 GB、Windows11配置,采用隨機(jī)生成的大規(guī)模數(shù)據(jù),生成不同的帶權(quán)有向圖進(jìn)行測(cè)試,表1中程序的運(yùn)行時(shí)間單位為ms,每一項(xiàng)測(cè)試均會(huì)隨機(jī)生成100組測(cè)試數(shù)據(jù),得到的2種算法的平均執(zhí)行時(shí)間如表1所示。其中,在用傳統(tǒng)算法測(cè)試序號(hào)4、5組數(shù)據(jù)時(shí),由于傳統(tǒng)算法時(shí)間復(fù)雜度呈指數(shù)級(jí)別規(guī)模增長(zhǎng),且數(shù)據(jù)規(guī)模過(guò)高,故無(wú)法在可接受的時(shí)間范圍內(nèi)運(yùn)算出結(jié)果。

表1 傳統(tǒng)算法與分層圖最短路算法執(zhí)行時(shí)間測(cè)試對(duì)比

由實(shí)驗(yàn)結(jié)果可以驗(yàn)證在大部分情況下,分層圖最短路算法的效率要遠(yuǎn)優(yōu)于傳統(tǒng)算法,且當(dāng)實(shí)驗(yàn)數(shù)據(jù)規(guī)模越大時(shí),分層圖最短路算法的性能優(yōu)勢(shì)會(huì)越明顯。

5 結(jié)語(yǔ)

本文針對(duì)在特定條件下的路徑選擇問(wèn)題提出了一種分層圖最短路算法,詳細(xì)分析了該算法的流程、效率、時(shí)間復(fù)雜度等,并在實(shí)驗(yàn)平臺(tái)將其與傳統(tǒng)求解算法相比較,驗(yàn)證了本文所提出的分層圖最短路算法具有更優(yōu)的性能效率。