王鈞盛,雷欣祺,房慧宇,孔揚濤

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

0 引言

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

1 相關(guān)定義

1.1 圖

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

1.2 最短路徑

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

2 傳統(tǒng)算法

2.1 算法執(zhí)行過程

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

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

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

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

(2)初始化:

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

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

小頂堆heap。

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

(4)while堆不空時。

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

從未處理點集S中刪除u。

對每個與u相鄰的節(jié)點vinG.Adj[u] do。

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

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

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

否則,將v加入堆。

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

此時,對所有節(jié)點v,dist[v]存儲的是從源點s到v的最短距離。

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

2.3 枚舉算法

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

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

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

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

3 分層圖最短路算法

3.1 分層圖

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

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

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

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

圖1 分層圖建模示例

3.3 算法執(zhí)行過程

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

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

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

(3)初始化:

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

dist[s]=0。

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

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

取Lk中的每個節(jié)點u。

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

更新dist[v]的值。

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

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

否則dist[v]保持為正無窮大。

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

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

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

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

否則輸出正無窮大,表示無路徑可達。

3.4 算法正確性分析

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

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

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

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

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

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

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

4 比較測試

4.1 算法比較

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

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

4.2 實驗測試

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

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

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

5 結(jié)語

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