基于并行計(jì)算的快速Dijkstra算法研究

葉穎詩(shī)，魏福義，蔡賢資

華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣州510000

1 引言

最短路徑問(wèn)題是一個(gè)經(jīng)典的計(jì)算問(wèn)題，它是計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，在很多領(lǐng)域具有廣泛的應(yīng)用，譬如物流線(xiàn)路優(yōu)化，GPS導(dǎo)航、社交網(wǎng)絡(luò)等?？焖儆?jì)算最短路徑，滿(mǎn)足其應(yīng)用的實(shí)時(shí)性是這些應(yīng)用的基本要求。常見(jiàn)的最短路徑算法有Dijkstra 算法、Floyd 算法、A*算法等。

Dijkstra 算法[1]是求解單源最短路徑算法中的經(jīng)典算法。對(duì)Dijkstra 的優(yōu)化引起了海內(nèi)外學(xué)者的廣泛關(guān)注。構(gòu)造特殊的數(shù)據(jù)結(jié)構(gòu)是常見(jiàn)的優(yōu)化手法，如堆[2]和最短路徑樹(shù)[3]等。文獻(xiàn)[4]提出了當(dāng)臨時(shí)性標(biāo)號(hào)t 相同時(shí)，將其同時(shí)標(biāo)記為永久性標(biāo)號(hào)p。隨著多核時(shí)代的到來(lái)，并行計(jì)算是解決此問(wèn)題的關(guān)鍵。文獻(xiàn)[5]首次提出并行異步更新標(biāo)號(hào)t 的優(yōu)化算法，其主要思想是使用多個(gè)隊(duì)列在共享儲(chǔ)存系統(tǒng)上實(shí)現(xiàn)更新。文獻(xiàn)[6]將并行算法通過(guò)OpenMP 引入到Dijkstra 算法中；文獻(xiàn)[7]將多線(xiàn)程運(yùn)用于交通網(wǎng)絡(luò)進(jìn)行子網(wǎng)分割中；文獻(xiàn)[8]通過(guò)Hadoop云平臺(tái)下采用MapReduce 并行編程提高算法效率。文獻(xiàn)[9-13]均為前人對(duì)最短路徑算法的并行優(yōu)化。

本文將多標(biāo)號(hào)的Dijkstra 算法和并行計(jì)算有機(jī)結(jié)合，給出了文獻(xiàn)[4]所提出的多標(biāo)號(hào)Dijkstra 算法新的證明；得到賦權(quán)正則樹(shù)對(duì)于三種算法的時(shí)間復(fù)雜度排序；采用Java編程進(jìn)行仿真實(shí)驗(yàn)，分析多標(biāo)號(hào)串行算法與并行算法的優(yōu)劣。實(shí)驗(yàn)結(jié)果表明，Dijkstra 多標(biāo)號(hào)并行算法能更好地提高計(jì)算最短路徑的效率。

2 Dijkstra算法及其優(yōu)化方向

本章給出了將Dijkstra算法優(yōu)化為串行算法和并行算法的理論基礎(chǔ)，給出了基于并行計(jì)算的Dijkstra算法。

2.1 Dijkstra算法思想

Dijkstra 算法是由荷蘭科學(xué)家Dijkstra 于1959 年首次提出[1]，此算法被敘述為初始化、求標(biāo)號(hào)p和修改標(biāo)號(hào)t三步。它可以有效地解決單源最短路徑問(wèn)題。該算法的主要特點(diǎn)是以起點(diǎn)為中心點(diǎn)向外延展，直至延展到終點(diǎn)為止，在此過(guò)程中獲得兩點(diǎn)間的最短路徑。

給定一個(gè)簡(jiǎn)單賦權(quán)圖G(V,E,W)，其中V 為圖G 的頂點(diǎn)集，E 為圖G 的邊集，W 為圖G 的邊權(quán)集。對(duì)于任意vi,vj∈V，若存在eij∈E，則邊eij的權(quán)wij為非負(fù)正實(shí)數(shù)；否則，wij=∞。

首先給出描述Dijkstra算法的基本定義。

定義1設(shè)li(r)*為頂點(diǎn)v1到頂點(diǎn)vi的最短路徑的權(quán)值，如果頂點(diǎn)vi在第r 步獲得了標(biāo)號(hào)li(r)*，則稱(chēng)頂點(diǎn)vi在Dijkstra算法的第r步獲得了永久性標(biāo)號(hào)p，其中r ≥0。

定義2設(shè)集合稱(chēng)為永久性標(biāo)號(hào)集合。其中任意vi∈Pr,vi獲得永久性標(biāo)號(hào)p；設(shè)集合Tr=V/Pr，其中Tr中的元素為在第r 步尚未獲得永久性標(biāo)號(hào)p的點(diǎn)集，Tr稱(chēng)為臨時(shí)性標(biāo)號(hào)集合。

定義3li(r)為頂點(diǎn)v0到頂點(diǎn)vi的最短路徑的上界，如果頂點(diǎn)在第r 步獲得li(r)，則稱(chēng)頂點(diǎn)vi在Dijkstra 算法的第r 步獲得了臨時(shí)性標(biāo)號(hào)t，其中r ≥0。當(dāng)v0與vi通過(guò)集合Tr不可達(dá)或i=0，則li(r)=∞。

2.2 優(yōu)化方向

文獻(xiàn)[4]提出，當(dāng)選取標(biāo)號(hào)p 時(shí)，面對(duì)多個(gè)頂點(diǎn)同時(shí)在第r 步擁有最小的標(biāo)號(hào)t時(shí)，應(yīng)該同時(shí)擁有標(biāo)號(hào)p。令這p 個(gè)頂點(diǎn)同時(shí)擁有標(biāo)號(hào)p，可以在一定程度上減少集合Tr歷遍次數(shù)，縮短計(jì)算時(shí)間，優(yōu)化算法計(jì)算效率。

定理1Dijkstra 標(biāo)號(hào)法中，在同一步將多個(gè)擁有最小標(biāo)號(hào)t的頂點(diǎn)標(biāo)記上標(biāo)號(hào)p，最短路的計(jì)算結(jié)果不變。

證明計(jì)算v0到圖G 的其他頂點(diǎn)的最短路徑。

當(dāng)r ＞0，若存在vi,vj∈Tr-1，使得

即vi,vj在第r 步中同時(shí)擁有被p 標(biāo)記的機(jī)會(huì)?，F(xiàn)在將頂點(diǎn)vi標(biāo)記為標(biāo)號(hào)p。接著進(jìn)行Dijkstra 算法的修改標(biāo)號(hào)t。

在此步不改變vj的標(biāo)號(hào)t 值。若需修改，則eij∈E。否則，由于。但,所以在此步不可能修改vj的標(biāo)號(hào)t 值。接下來(lái)Dijkstra算法找尋新的標(biāo)號(hào)p。

假設(shè)在此r 步內(nèi)選取不到vj標(biāo)記為標(biāo)號(hào)p，則存在vm，使得

當(dāng)lm

(r)在第r 步被修改過(guò)，則

當(dāng)lm(r)在第r 步被未修改過(guò)，,但矛盾。

綜上，在第r 步可以選到vj作為標(biāo)號(hào)p，選擇的次序并不影響后面的操作。所以不影響計(jì)算結(jié)果。

運(yùn)用此定理，可減少選取標(biāo)號(hào)p 的次數(shù)，從而縮短算法的運(yùn)行時(shí)間，達(dá)到提高算法效率的目的。本文將此思想加入到優(yōu)化算法中，稱(chēng)該算法為多標(biāo)號(hào)的Dijkstra算法。

2.3 多標(biāo)號(hào)的Dijkstra并行算法

分治法，就是“分而治之”，將一個(gè)復(fù)雜的問(wèn)題分為若干個(gè)相似的子問(wèn)題，而子問(wèn)題能用簡(jiǎn)單的方式直接求解。并行計(jì)算正是使用分治的思想，使用多個(gè)處理器來(lái)協(xié)同解決同類(lèi)問(wèn)題，分別對(duì)原問(wèn)題的子問(wèn)題同時(shí)求解，以增加算法效率。使用多線(xiàn)程并行計(jì)算的目的是充分使用CPU 資源，使其在較短的時(shí)間內(nèi)完成計(jì)算，進(jìn)而提升整體處理性能。如圖1所示，圖中的Δt 則為節(jié)省的時(shí)間。

圖1 并行計(jì)算效率提升示意圖

隨著研究問(wèn)題規(guī)模的擴(kuò)大，傳統(tǒng)的串行計(jì)算技術(shù)難以滿(mǎn)足對(duì)其計(jì)算能力的需求。文獻(xiàn)[4]中的多標(biāo)號(hào)Dijkstra算法將多個(gè)擁有最小li(r)的頂點(diǎn)同時(shí)標(biāo)記上永久性標(biāo)號(hào)p 時(shí)，多標(biāo)號(hào)的Dijkstra 算法（3）中修改標(biāo)號(hào)t 變得復(fù)雜了。由于此步僅修改獲得永久性標(biāo)號(hào)p 頂點(diǎn)的鄰點(diǎn)，導(dǎo)致多標(biāo)號(hào)的Dijkstra需要修改的點(diǎn)數(shù)增加。

如圖2 所示，經(jīng)典的Dijkstra 算法將一個(gè)點(diǎn)（點(diǎn)1）選為永久性標(biāo)號(hào)p，它的鄰點(diǎn)（點(diǎn)2、點(diǎn)8、點(diǎn)9）將需要修改臨時(shí)標(biāo)號(hào)t；然而多標(biāo)號(hào)的Dijkstra 同時(shí)將三個(gè)點(diǎn)（點(diǎn)1、點(diǎn)2、點(diǎn)3）選為永久性標(biāo)號(hào)，則它需要修改這些點(diǎn)所有鄰點(diǎn)的臨時(shí)性標(biāo)號(hào)（點(diǎn)3、點(diǎn)4、點(diǎn)5、點(diǎn)6、點(diǎn)7、點(diǎn)9）。由此可得多標(biāo)號(hào)的Dijkstra修改臨時(shí)性標(biāo)號(hào)的工作量被增加了。因此考慮將并行算法融入到多標(biāo)號(hào)的Dijkstra算法之中。

圖2 兩種算法修改臨時(shí)性標(biāo)號(hào)工作量對(duì)比

當(dāng)有多個(gè)線(xiàn)程同時(shí)運(yùn)行并試圖訪(fǎng)問(wèn)同一個(gè)公共資源時(shí)，會(huì)出現(xiàn)資源爭(zhēng)奪的問(wèn)題，從而影響程序執(zhí)行的效率和正確性，這種現(xiàn)象被稱(chēng)為非線(xiàn)程安全。為了避免非線(xiàn)程安全，需要保證這些公共資源只有一個(gè)線(xiàn)程在使用它。在多標(biāo)號(hào)的Dijkstra算法中，儲(chǔ)存標(biāo)號(hào)t的數(shù)組作為此并行算法的共享數(shù)據(jù)。在此根據(jù)所在實(shí)驗(yàn)平臺(tái)的CPU 的線(xiàn)程數(shù)，分配各個(gè)線(xiàn)程的工作量，讓線(xiàn)程固定處理若干個(gè)頂點(diǎn)的標(biāo)號(hào)t值，從而做到數(shù)據(jù)獨(dú)立，達(dá)到線(xiàn)程安全。如圖3所示，假設(shè)數(shù)組長(zhǎng)度為8，線(xiàn)程數(shù)為4，則每個(gè)線(xiàn)程為其分配兩個(gè)頂點(diǎn)進(jìn)行工作。

圖3 線(xiàn)程分配示意圖

假設(shè)計(jì)算v1到其他點(diǎn)的最短路徑，多標(biāo)號(hào)Dijkstra并行算法流程圖如圖4所示。

3 三種算法的時(shí)間復(fù)雜度

算法的效率常用時(shí)間復(fù)雜度作為評(píng)判指標(biāo)。針對(duì)賦權(quán)正則樹(shù)，分析了經(jīng)典Dijkstra算法，多標(biāo)號(hào)的Dijkstra串行算法和多標(biāo)號(hào)的Dijkstra 并行算法的時(shí)間復(fù)雜度，并且給出其排序。

由于并行算法所節(jié)約的遍歷次數(shù)與各實(shí)驗(yàn)平臺(tái)處理器性能有關(guān)，計(jì)算其算法復(fù)雜度比較困難。本文試構(gòu)造特殊圖，在求標(biāo)號(hào)p 步驟中，可以使得多個(gè)頂點(diǎn)同時(shí)擁有永久性標(biāo)號(hào)p。在計(jì)算時(shí)間復(fù)雜度時(shí)，算法優(yōu)化程度能達(dá)到極限。

若圖中任意兩個(gè)頂點(diǎn)之間都有邊相連，此圖稱(chēng)為完全圖，記為B。若它的頂點(diǎn)數(shù)為n，則邊數(shù)為，即n(n-1)/2。當(dāng)圖的邊數(shù)遠(yuǎn)遠(yuǎn)少于完全圖，這樣的圖稱(chēng)為稀疏圖；反之，則稱(chēng)為稠密圖。

無(wú)圈的連通圖稱(chēng)為樹(shù)，記為T(mén)。給定一個(gè)樹(shù)T( m, h;w1,w2,…,wh)，在此樹(shù)中任意非葉子節(jié)點(diǎn)的出度都相同，記為m；從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)依次經(jīng)過(guò)的節(jié)點(diǎn)（含根、葉節(jié)點(diǎn)）形成樹(shù)T 的最長(zhǎng)路徑稱(chēng)為深度，記為h；當(dāng)根節(jié)點(diǎn)到兩個(gè)節(jié)點(diǎn)的的路徑長(zhǎng)度相同，則這兩個(gè)節(jié)點(diǎn)處于同一層，第r(r=1,2,…,h層)的節(jié)點(diǎn)的出度上的權(quán)數(shù)相同，記為wr。此種樹(shù)T 稱(chēng)為賦權(quán)正則樹(shù)。賦權(quán)正則樹(shù)T( 3, 2;1,2)，見(jiàn)圖5。

圖4 多標(biāo)號(hào)Dijkstra并行算法流程圖

圖5 正則樹(shù)示意圖

3.1 時(shí)間復(fù)雜度排序

下面針對(duì)賦權(quán)正則樹(shù)T( m, h;w1,w2,…,wh)的結(jié)構(gòu)對(duì)時(shí)間復(fù)雜度進(jìn)行分析。

定理2對(duì)于賦權(quán)正則樹(shù)T( m, h;w1,w2,…,wh)，傳統(tǒng)的Dijkstra 算法，多標(biāo)號(hào)的Dijkstra 串行算法，多標(biāo)號(hào)的Dijkstra并行算法時(shí)間復(fù)雜度依次降低。

證明

（1）傳統(tǒng)的Dijkstra

使用線(xiàn)性搜索計(jì)算最大標(biāo)號(hào)p 的Dijkstra 算法，其時(shí)間復(fù)雜度為O(n2)[1]。文獻(xiàn)[14]通過(guò)斐波那契堆儲(chǔ)存標(biāo)號(hào)p，其時(shí)間復(fù)雜度下降到O(n lg n+m)，其中n 表示頂點(diǎn)數(shù)，m 表示邊數(shù)。

（2）串行多標(biāo)號(hào)的Dijkstra

串行算法外循環(huán)的時(shí)間復(fù)雜度為O(h)，使用二分法選取標(biāo)號(hào)p 的時(shí)間復(fù)雜度為O(lg n)，修改標(biāo)號(hào)t 的時(shí)間復(fù)雜度為O(n),因此其總的時(shí)間復(fù)雜度為O(h(n+lg n))。

（3）并行多標(biāo)號(hào)的Dijkstra

并行算法假設(shè)實(shí)驗(yàn)平臺(tái)支持l 條線(xiàn)程同時(shí)工作，在理想的狀況下，修改標(biāo)號(hào)t 的時(shí)間復(fù)雜度從O(n)下降到O(n/l)。因此其總的時(shí)間復(fù)雜度為O(h(n/l+lg n))。O(n2)＞O(h(n+lg n))＞O(h(n/l+lg n))定理成立。

3.2 準(zhǔn)確性分析

時(shí)間復(fù)雜度計(jì)算是基于理想狀態(tài)下的算法效率衡量，下面對(duì)此時(shí)間復(fù)雜度進(jìn)行準(zhǔn)確性分析。

針對(duì)并行多標(biāo)號(hào)的Dijkstra 算法，并行計(jì)算中線(xiàn)程的切換需要耗費(fèi)一定的時(shí)間成本，在同一操作平臺(tái)下，此時(shí)間成本記為T(mén)。由定理2 可知：理想狀態(tài)下并行多標(biāo)號(hào)的Dijkstra 算法時(shí)間復(fù)雜度為O(h(n/l+lg n))。則現(xiàn)實(shí)狀態(tài)與理想狀態(tài)的時(shí)間復(fù)雜度比值為：

當(dāng)n較小時(shí)，從理論上說(shuō)，由于T的存在，此值大于1，優(yōu)化提速與線(xiàn)程開(kāi)銷(xiāo)抵消，運(yùn)用傳統(tǒng)算法計(jì)算時(shí)間相對(duì)于兩種優(yōu)化，計(jì)算時(shí)間也較短，優(yōu)化效果不明顯。由于

當(dāng)n 逐漸增大時(shí)，此值逐漸接近1，算法出現(xiàn)正優(yōu)化，時(shí)間復(fù)雜度與算法速率呈正相關(guān)，說(shuō)明此復(fù)雜度計(jì)算的準(zhǔn)確性。

當(dāng)固定圖規(guī)模n 時(shí)，非葉子節(jié)點(diǎn)m 越大，深度則越小，則并行多標(biāo)號(hào)的Dijkstra算法的時(shí)間復(fù)雜度越小，計(jì)算速率越高。

4 仿真實(shí)驗(yàn)

本文搭建了單機(jī)版的實(shí)驗(yàn)平臺(tái)。實(shí)驗(yàn)平臺(tái)的硬件環(huán)境為Intel?CoreTM，且有四個(gè)3.6 GHz 的內(nèi)核CPU，在硬件上支持八線(xiàn)程并行，機(jī)器上運(yùn)行Windows 10 專(zhuān)業(yè)版（x64）的操作系統(tǒng)，內(nèi)存為8 GB，利用Java 語(yǔ)言編程實(shí)現(xiàn)。

4.1 實(shí)驗(yàn)指標(biāo)和目的

針對(duì)稠密圖和特殊類(lèi)型的非稠密圖（正則樹(shù)）兩類(lèi)圖，共設(shè)計(jì)四種實(shí)驗(yàn)，采用運(yùn)行時(shí)間和并行加速比兩個(gè)指標(biāo)，刻畫(huà)Dijkstra 算法，多標(biāo)號(hào)的Dijkstra 串行算法和多標(biāo)號(hào)的Dijkstra并行算法的運(yùn)行效率。設(shè)計(jì)實(shí)驗(yàn)顯示對(duì)Dijkstra算法的優(yōu)化效果。

本文用于衡量算法優(yōu)化程度的指標(biāo)為運(yùn)行時(shí)間和并行加速比。

（1）運(yùn)行時(shí)間

運(yùn)行時(shí)間作為判斷程序效率的常見(jiàn)指標(biāo)，能較好地體現(xiàn)優(yōu)化效果。

（2）并行加速比

并行加速比是用于衡量程序并行化的性能和效果的一個(gè)常見(jiàn)指標(biāo)。其計(jì)算方法為串行計(jì)算程序和并行計(jì)算程序中的運(yùn)行時(shí)間比率，公式如下：

Sp=T1/Tp

其中p為CPU數(shù)量，T1為傳統(tǒng)Dijkstra算法的執(zhí)行時(shí)間，Tp為當(dāng)有p 個(gè)處理器時(shí)，并行算法的執(zhí)行時(shí)間，Sp稱(chēng)為當(dāng)有p 個(gè)處理器時(shí)的加速比。當(dāng)Sp=p 時(shí)，稱(chēng)此加速比為線(xiàn)性加速比，又稱(chēng)為理想加速比。所以，當(dāng)并行加速比的數(shù)值越接近處理器數(shù)量，程序的并行優(yōu)化程度越好。

設(shè)計(jì)下列實(shí)驗(yàn)，驗(yàn)證基于多標(biāo)號(hào)的串行算法與并行算法對(duì)Dijkstra算法的優(yōu)化效果。

4.2 仿真設(shè)計(jì)與數(shù)據(jù)

在數(shù)據(jù)結(jié)構(gòu)中，常見(jiàn)的表示結(jié)構(gòu)有兩種：鄰接矩陣和鄰接表。

鄰接矩陣是使用二維數(shù)組模擬線(xiàn)性代數(shù)中矩陣的結(jié)構(gòu)。此種數(shù)據(jù)結(jié)構(gòu)所使用的儲(chǔ)存空間較大，但其使用較為便捷。

鄰接表使用單鏈表數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。數(shù)組的下標(biāo)為頂點(diǎn)的標(biāo)號(hào)，每一個(gè)數(shù)組元素指向一個(gè)單鏈表。單鏈表中的元素則是頂點(diǎn)下標(biāo)所指頂?shù)泥忺c(diǎn)。鏈表中的元素?cái)?shù)據(jù)結(jié)構(gòu)如圖6 所示，每個(gè)元素代表其所在數(shù)組下標(biāo)所表示的頂點(diǎn)與鏈表元素中頂點(diǎn)編號(hào)所示頂點(diǎn)有邊相連，“邊權(quán)值”代表該邊的權(quán)值，“下一個(gè)元素地址”表示下一個(gè)鏈表元素以此形成鏈表的結(jié)構(gòu)。

圖6 單鏈表元素?cái)?shù)據(jù)結(jié)構(gòu)

將所有鏈表以數(shù)組的形式存放到一起，具體轉(zhuǎn)換形式如圖7。

圖7 圖結(jié)構(gòu)與鄰接表的轉(zhuǎn)換示意圖

當(dāng)圖的頂點(diǎn)數(shù)較大時(shí)，節(jié)省內(nèi)存空間選擇鄰接表表示無(wú)向圖。設(shè)計(jì)兩類(lèi)數(shù)據(jù)圖進(jìn)行實(shí)驗(yàn)。

（1）權(quán)值滿(mǎn)足泊松分布的隨機(jī)稠密圖

為驗(yàn)證一般圖與本優(yōu)化算法的貼合度，特設(shè)計(jì)一般隨機(jī)圖進(jìn)行實(shí)驗(yàn)，圖的權(quán)值符合泊松分布[15]。通過(guò)觀察三種算法在此圖中兩種指標(biāo)的狀況，研究圖的頂點(diǎn)規(guī)模與兩種算法的優(yōu)化性能。本實(shí)驗(yàn)將稠密圖頂點(diǎn)數(shù)與邊數(shù)的比例控制在1∶5 左右，即將此數(shù)據(jù)集的點(diǎn)邊比控制0.2 左右，令邊的權(quán)值分布符合泊松分布，以此控制頂點(diǎn)數(shù)觀察圖規(guī)模與優(yōu)化性能之間的關(guān)系點(diǎn)邊規(guī)模如表1所示。

表1 泊松分布隨機(jī)圖邊點(diǎn)規(guī)模

（2）非稠密圖-正則樹(shù)

多標(biāo)號(hào)的Dijkstra 串行算法對(duì)于Dijkstra 算法的優(yōu)化著重于在每一步選取永久性標(biāo)號(hào)p，當(dāng)每一步選取的節(jié)點(diǎn)越多，此算法的優(yōu)化效率應(yīng)越明顯。

計(jì)算最短路徑一般面向稀疏圖。本實(shí)驗(yàn)通過(guò)正則樹(shù)探求兩種優(yōu)化算法所適應(yīng)的圖的一般情況。研究樹(shù)的非葉子節(jié)點(diǎn)的出度、深度與本算法優(yōu)化之間的關(guān)系，設(shè)計(jì)出三種類(lèi)型的正則樹(shù)進(jìn)行實(shí)驗(yàn)。

①固定深度，以非葉子節(jié)點(diǎn)的出度為變量。

為考察非葉子節(jié)點(diǎn)出度與優(yōu)化效果之間的關(guān)系，此實(shí)驗(yàn)固定深度以非葉子節(jié)點(diǎn)的出度作為變量進(jìn)行實(shí)驗(yàn)。固定圖的深度為4，令任意非葉子節(jié)點(diǎn)的出度逐漸增大，出度與節(jié)點(diǎn)數(shù)量的關(guān)系如表2所示。

表2 深度為4的出度與節(jié)點(diǎn)數(shù)關(guān)系

②固定圖頂點(diǎn)規(guī)模，以非葉子節(jié)點(diǎn)的出度為變量。

優(yōu)化算法優(yōu)化程度與頂點(diǎn)規(guī)模有關(guān)。頂點(diǎn)規(guī)模與運(yùn)行時(shí)間成負(fù)相關(guān)。固定圖頂點(diǎn)規(guī)模，以非葉子節(jié)點(diǎn)的出度為變量，觀察其優(yōu)化效率。固定圖頂點(diǎn)數(shù)為6 000，令任意非葉子節(jié)點(diǎn)的出度逐漸增大，使得深度隨之變淺。非葉子節(jié)點(diǎn)的出度與深度之間的關(guān)系如表3所示。

表3 頂點(diǎn)數(shù)為6 000的深度與出度之間的關(guān)系

③固定非葉子節(jié)點(diǎn)的出度，以深度為變量。

深度作為正則樹(shù)的層數(shù)，最大程度地影響正則樹(shù)的頂點(diǎn)規(guī)模，此實(shí)驗(yàn)研究深度與優(yōu)化算法效率之間的關(guān)系。固定圖的非葉子節(jié)點(diǎn)的出度為2，令其深度逐漸增大，深度與節(jié)點(diǎn)數(shù)之間的關(guān)系如表4所示。

表4 出度為2的深度與節(jié)點(diǎn)數(shù)關(guān)系

通過(guò)兩種實(shí)驗(yàn)數(shù)據(jù)設(shè)計(jì)，應(yīng)用運(yùn)行時(shí)間和并行加速比兩個(gè)指標(biāo)，分析其優(yōu)化程度，獲得其算法優(yōu)越性。

4.3 實(shí)驗(yàn)結(jié)果與分析

4.3.1 權(quán)值滿(mǎn)足泊松分布的隨機(jī)稠密圖實(shí)驗(yàn)分析

程序運(yùn)行時(shí)間如圖8所示，多標(biāo)號(hào)p的Dijkstra算法對(duì)傳統(tǒng)的Dijkstra算法有明顯的改進(jìn)。且當(dāng)圖的頂點(diǎn)數(shù)越多，多標(biāo)號(hào)的Dijkstra串行算法對(duì)Dijkstra算法的效率改進(jìn)越明顯，最高在頂點(diǎn)數(shù)為20 000 上節(jié)約995 ms（見(jiàn)圖8點(diǎn)A、B）。

圖8 泊松分布隨機(jī)圖運(yùn)行時(shí)間

基于并行計(jì)算的Dijkstra算法又在多標(biāo)號(hào)p 的Dijk‐stra算法優(yōu)化的基礎(chǔ)上，進(jìn)一步提高了計(jì)算效率，優(yōu)化程度見(jiàn)圖8。可見(jiàn)兩種優(yōu)化都比傳統(tǒng)的Dijkstra 的計(jì)算速度快，且優(yōu)化程度隨著圖規(guī)模的增大而增大。多次重復(fù)實(shí)驗(yàn)也同樣顯示此規(guī)律。

實(shí)驗(yàn)表明本方法對(duì)傳統(tǒng)Dijkstra 算法的優(yōu)化效果明顯。下面以并行加速比評(píng)判并行算法對(duì)多標(biāo)號(hào)p 的Dijkstra算法的優(yōu)化程度。

從并行加速比的數(shù)據(jù)可得：隨著圖頂點(diǎn)規(guī)模的擴(kuò)大，加速比呈增長(zhǎng)的趨勢(shì)。由于線(xiàn)程開(kāi)銷(xiāo)的問(wèn)題，圖頂點(diǎn)規(guī)模6 000 以下的加速比小于1。此現(xiàn)象表明當(dāng)圖頂點(diǎn)的規(guī)模較小時(shí)，使用并行的優(yōu)化的效果不明顯。但當(dāng)數(shù)據(jù)頂點(diǎn)規(guī)模到達(dá)6 000 點(diǎn)時(shí)，加速比已經(jīng)達(dá)到1.05（見(jiàn)圖9點(diǎn)A），6 000以上的圖加速比都能處于較優(yōu)的位置。當(dāng)數(shù)據(jù)頂點(diǎn)規(guī)模為20 000點(diǎn)時(shí)，加速比為3.49（見(jiàn)圖9點(diǎn)B），此時(shí)已經(jīng)較為接近理想加速比。

圖9 正態(tài)數(shù)據(jù)的并行加速比

上述兩個(gè)指標(biāo)的數(shù)據(jù)表明，Dijkstra算法的多標(biāo)號(hào)p優(yōu)化對(duì)于稠密圖有較好的優(yōu)化效果，計(jì)算效率有明顯的提升。對(duì)于大數(shù)據(jù)集合，算法的并行優(yōu)化比串行優(yōu)化效率更高。說(shuō)明本文的并行算法優(yōu)化對(duì)稠密圖模型的計(jì)算有較好的效果。

另一方面，對(duì)于節(jié)點(diǎn)數(shù)較小的圖，其優(yōu)化效果不明顯。原因是由于并行計(jì)算中線(xiàn)程的切換需要耗費(fèi)一定的時(shí)間成本，算法的優(yōu)化程度被此時(shí)間成本一定程度地抵消一部分，優(yōu)化效果不明顯。因此本算法更適用于規(guī)模較大的模型。

4.3.2 正則樹(shù)實(shí)驗(yàn)數(shù)據(jù)分析

（1）固定深度，以非葉子節(jié)點(diǎn)的出度為變量。

在相同的深度下（固定深度為4），不同的非葉子節(jié)點(diǎn)出度的程序運(yùn)行時(shí)間如圖10 所示。在深度為4 的情況下，非葉子節(jié)點(diǎn)的出度為14 時(shí)（見(jiàn)圖10 點(diǎn)A、B、C），頂點(diǎn)數(shù)為2 955。非葉子節(jié)點(diǎn)的出度小于14 時(shí)，三種算法的運(yùn)行時(shí)間相差不大，甚至出現(xiàn)有負(fù)優(yōu)化的現(xiàn)象，這是優(yōu)化效果被線(xiàn)程開(kāi)銷(xiāo)抵消的結(jié)果。當(dāng)非葉子節(jié)點(diǎn)的出度大于14 時(shí)，多標(biāo)號(hào)p 的Dijkstra 算法相對(duì)于傳統(tǒng)Dijkstra 算法的計(jì)算效率明顯提高，優(yōu)化效果大于線(xiàn)程開(kāi)銷(xiāo)，使得優(yōu)化效果呈現(xiàn)正面效果。而另一方面，基于并行計(jì)算的Dijkstra 算法對(duì)比于多標(biāo)號(hào)p 的Dijkstra 算法更加高效。

圖10 正則樹(shù)中不同出度的運(yùn)行時(shí)間

并行加速比的變化如圖11 所示。在深度為4 的情況下，非葉子節(jié)點(diǎn)出度等于18 的情況下，并行加速比達(dá)到1（見(jiàn)圖11 點(diǎn)A），往后隨著非葉子節(jié)點(diǎn)出度的增大，并行加速比逐漸增大，且在非葉子節(jié)點(diǎn)出度達(dá)到26 時(shí)，并行加速比達(dá)到2.12（見(jiàn)圖11 點(diǎn)B），處于較優(yōu)的狀況。觀察并行加速比指標(biāo)，說(shuō)明了并行優(yōu)化對(duì)于多標(biāo)號(hào)Dijkstra算法的優(yōu)化明顯。

圖11 正則樹(shù)中不同出度的并行加速比

（2）固定圖頂點(diǎn)規(guī)模，以非葉子節(jié)點(diǎn)的出度為變量。

在固定頂點(diǎn)規(guī)模的圖中，不同的非葉子節(jié)點(diǎn)出度的運(yùn)行時(shí)間如圖12所示。當(dāng)頂點(diǎn)出度為2時(shí)，優(yōu)化效果較差，但當(dāng)非葉子節(jié)點(diǎn)出度逐漸增加，優(yōu)化效果逐漸變好；當(dāng)非葉子節(jié)點(diǎn)的出度達(dá)到4 時(shí)，其呈現(xiàn)正相關(guān)的優(yōu)化效果（圖12 點(diǎn)A、B、C）。且隨著非葉子節(jié)點(diǎn)的出度的增加，優(yōu)化效果越來(lái)越好。對(duì)于并行加速比，如圖13 所示，在非葉子節(jié)點(diǎn)出度大于3 時(shí)，并行計(jì)算對(duì)此算法有正面影響，且隨著非葉子節(jié)點(diǎn)的增加而增加。

圖12 正則樹(shù)同樣頂點(diǎn)規(guī)模下不同出度的運(yùn)行時(shí)間

圖13 正則樹(shù)同樣頂點(diǎn)規(guī)模下不同出度的并行加速比

實(shí)驗(yàn)表明：基于并行計(jì)算的Dijkstra 算法的優(yōu)化效果與非葉子節(jié)點(diǎn)的出度有關(guān)，但當(dāng)出度較小時(shí)，效果并不明顯。

（3）固定非葉子節(jié)點(diǎn)的出度，以深度為變量。

在非葉子節(jié)點(diǎn)出度同時(shí)為2 的情況下，不同深度類(lèi)正則圖的程序運(yùn)行時(shí)間如圖14 所示。當(dāng)深度小于12時(shí)，優(yōu)化算法對(duì)傳統(tǒng)Dijkstra算法效率的提升并不明顯。在非葉子節(jié)點(diǎn)的出度為2 的情況下，深度為12 時(shí)，頂點(diǎn)數(shù)為4 095，頂點(diǎn)規(guī)模較小，說(shuō)明優(yōu)化效果不理想的原因?yàn)閳D的頂點(diǎn)規(guī)模較小。當(dāng)深度大于12，兩種優(yōu)化算法的運(yùn)行時(shí)間明顯短與傳統(tǒng)Dijkstra 算法（見(jiàn)圖14 點(diǎn)A、B、C）。

圖14 正則樹(shù)中不同深度的運(yùn)行時(shí)間

在非葉子節(jié)點(diǎn)出度同時(shí)為2 的情況下，深度大于12類(lèi)正則圖的并行加速比都能大于1（見(jiàn)圖15 點(diǎn)A）。此實(shí)驗(yàn)說(shuō)明頂點(diǎn)規(guī)模大于4 095 時(shí)，三種算法都有明顯不同，優(yōu)化效果較好。

圖15 正則樹(shù)中不同出度的并行加速比

4.4 算法推廣實(shí)驗(yàn)

此算法已被深圳微達(dá)安公司用于改進(jìn)基于柵格模型的室內(nèi)導(dǎo)航系統(tǒng)?；跂鸥衲Ｐ偷氖覂?nèi)導(dǎo)航模型是將平面圖劃分為若干大小相同的柵格，通過(guò)相鄰柵格之間的關(guān)系構(gòu)建的無(wú)向圖模型。它的任意點(diǎn)都擁有若干條距離相同的鄰邊。下面通過(guò)實(shí)驗(yàn)驗(yàn)證優(yōu)化算法的有效性。

實(shí)驗(yàn)環(huán)境為30 m×40 m 的室內(nèi)空間，一共八個(gè)房間，平面圖按照一定規(guī)則分為4 096個(gè)柵格，相鄰柵格定義邊相連，構(gòu)建具有4 096個(gè)頂點(diǎn)的無(wú)向圖模型，具有指定起點(diǎn)和終點(diǎn)運(yùn)用。三種算法的運(yùn)行時(shí)間如表5所示。

表5 柵格模型圖中兩種算法運(yùn)行時(shí)間對(duì)比

多標(biāo)號(hào)的Dijkstra串行和并行算法計(jì)算速率均高于傳統(tǒng)的Dijkstra，且使用并行計(jì)算速率更高。可見(jiàn)優(yōu)化算法在此現(xiàn)實(shí)場(chǎng)景中有較好的計(jì)算效率。

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

對(duì)于賦權(quán)正則樹(shù)，證明了多標(biāo)號(hào)Dijkstra 串行算法時(shí)間復(fù)雜度為O(h(n+lg n；)多)標(biāo)號(hào)的Dijkstra 并行算法時(shí)間復(fù)雜度為O(h(n/l+lg n;)都)優(yōu)于傳統(tǒng)Dijkstra 的時(shí)間復(fù)雜度O(n2)。通過(guò)仿真實(shí)驗(yàn)，也驗(yàn)證了時(shí)間復(fù)雜度排序的正確性。多標(biāo)號(hào)p 的Dijkstra 算法對(duì)于較為稠密的一般圖，具有較好的優(yōu)化效率；對(duì)于并行優(yōu)化，在頂點(diǎn)規(guī)模較大的（頂點(diǎn)數(shù)大于6 000）圖有較優(yōu)的優(yōu)化效率。對(duì)于正則樹(shù)，非葉子節(jié)點(diǎn)出度和深度對(duì)于兩種優(yōu)化算法的優(yōu)化效率都有影響。當(dāng)固定正則樹(shù)的深度為4 時(shí)，非葉子節(jié)點(diǎn)的出度超過(guò)14 時(shí)，兩種優(yōu)化算法的優(yōu)化效率都與非葉子節(jié)點(diǎn)的出度成正相關(guān)；當(dāng)固定非葉子節(jié)點(diǎn)為2時(shí)，當(dāng)正則樹(shù)的深度大于12時(shí)，兩種優(yōu)化算法對(duì)Dijks‐tra 算法有正優(yōu)化的效果；在同樣的圖頂點(diǎn)規(guī)模下，當(dāng)非葉子節(jié)點(diǎn)的出度大于3 時(shí)，兩種優(yōu)化算法的優(yōu)化效率都與非葉子節(jié)點(diǎn)的出度成正相關(guān)。相對(duì)于文獻(xiàn)[2]的并行優(yōu)化，本文的并行優(yōu)化的并行加速比高于其最高的2.06。

由公式（1）可知，本文的優(yōu)化算法對(duì)于頂點(diǎn)數(shù)較大的稠密圖都有很好的優(yōu)化效果。對(duì)于非稠密圖，當(dāng)圖的頂點(diǎn)向外鄰點(diǎn)數(shù)基本一致時(shí)，此時(shí)圖與正則樹(shù)相似，也適用于本優(yōu)化算法。