葉穎詩，魏福義，蔡賢資

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

1 引言

最短路徑問題是一個經(jīng)典的計算問題，它是計算一個節(jié)點到其他節(jié)點的最短路徑，在很多領域具有廣泛的應用，譬如物流線路優(yōu)化，GPS導航、社交網(wǎng)絡等?？焖儆嬎阕疃搪窂剑瑵M足其應用的實時性是這些應用的基本要求。常見的最短路徑算法有Dijkstra 算法、Floyd 算法、A*算法等。

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

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

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

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

2.1 Dijkstra算法思想

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

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

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

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

定義2設集合稱為永久性標號集合。其中任意vi∈Pr,vi獲得永久性標號p；設集合Tr=V/Pr，其中Tr中的元素為在第r 步尚未獲得永久性標號p的點集，Tr稱為臨時性標號集合。

定義3li(r)為頂點v0到頂點vi的最短路徑的上界，如果頂點在第r 步獲得li(r)，則稱頂點vi在Dijkstra 算法的第r 步獲得了臨時性標號t，其中r ≥0。當v0與vi通過集合Tr不可達或i=0，則li(r)=∞。

2.2 優(yōu)化方向

文獻[4]提出，當選取標號p 時，面對多個頂點同時在第r 步擁有最小的標號t時，應該同時擁有標號p。令這p 個頂點同時擁有標號p，可以在一定程度上減少集合Tr歷遍次數(shù)，縮短計算時間，優(yōu)化算法計算效率。

定理1Dijkstra 標號法中，在同一步將多個擁有最小標號t的頂點標記上標號p，最短路的計算結(jié)果不變。

證明計算v0到圖G 的其他頂點的最短路徑。

當r ＞0，若存在vi,vj∈Tr-1，使得

即vi,vj在第r 步中同時擁有被p 標記的機會?，F(xiàn)在將頂點vi標記為標號p。接著進行Dijkstra 算法的修改標號t。

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

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

當lm

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

當lm(r)在第r 步被未修改過，,但矛盾。

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

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

2.3 多標號的Dijkstra并行算法

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

圖1 并行計算效率提升示意圖

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

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

圖2 兩種算法修改臨時性標號工作量對比

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

圖3 線程分配示意圖

假設計算v1到其他點的最短路徑，多標號Dijkstra并行算法流程圖如圖4所示。

3 三種算法的時間復雜度

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

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

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

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

圖4 多標號Dijkstra并行算法流程圖

圖5 正則樹示意圖

3.1 時間復雜度排序

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

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

證明

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

使用線性搜索計算最大標號p 的Dijkstra 算法，其時間復雜度為O(n2)[1]。文獻[14]通過斐波那契堆儲存標號p，其時間復雜度下降到O(n lg n+m)，其中n 表示頂點數(shù)，m 表示邊數(shù)。

（2）串行多標號的Dijkstra

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

（3）并行多標號的Dijkstra

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

3.2 準確性分析

時間復雜度計算是基于理想狀態(tài)下的算法效率衡量，下面對此時間復雜度進行準確性分析。

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

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

當n 逐漸增大時，此值逐漸接近1，算法出現(xiàn)正優(yōu)化，時間復雜度與算法速率呈正相關，說明此復雜度計算的準確性。

當固定圖規(guī)模n 時，非葉子節(jié)點m 越大，深度則越小，則并行多標號的Dijkstra算法的時間復雜度越小，計算速率越高。

4 仿真實驗

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

4.1 實驗指標和目的

針對稠密圖和特殊類型的非稠密圖（正則樹）兩類圖，共設計四種實驗，采用運行時間和并行加速比兩個指標，刻畫Dijkstra 算法，多標號的Dijkstra 串行算法和多標號的Dijkstra并行算法的運行效率。設計實驗顯示對Dijkstra算法的優(yōu)化效果。

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

（1）運行時間

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

（2）并行加速比

并行加速比是用于衡量程序并行化的性能和效果的一個常見指標。其計算方法為串行計算程序和并行計算程序中的運行時間比率，公式如下：

Sp=T1/Tp

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

設計下列實驗，驗證基于多標號的串行算法與并行算法對Dijkstra算法的優(yōu)化效果。

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

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

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

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

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

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

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

當圖的頂點數(shù)較大時，節(jié)省內(nèi)存空間選擇鄰接表表示無向圖。設計兩類數(shù)據(jù)圖進行實驗。

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

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

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

（2）非稠密圖-正則樹

多標號的Dijkstra 串行算法對于Dijkstra 算法的優(yōu)化著重于在每一步選取永久性標號p，當每一步選取的節(jié)點越多，此算法的優(yōu)化效率應越明顯。

計算最短路徑一般面向稀疏圖。本實驗通過正則樹探求兩種優(yōu)化算法所適應的圖的一般情況。研究樹的非葉子節(jié)點的出度、深度與本算法優(yōu)化之間的關系，設計出三種類型的正則樹進行實驗。

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

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

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

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

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

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

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

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

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

通過兩種實驗數(shù)據(jù)設計，應用運行時間和并行加速比兩個指標，分析其優(yōu)化程度，獲得其算法優(yōu)越性。

4.3 實驗結(jié)果與分析

4.3.1 權(quán)值滿足泊松分布的隨機稠密圖實驗分析

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

圖8 泊松分布隨機圖運行時間

基于并行計算的Dijkstra算法又在多標號p 的Dijk‐stra算法優(yōu)化的基礎上，進一步提高了計算效率，優(yōu)化程度見圖8?？梢妰煞N優(yōu)化都比傳統(tǒng)的Dijkstra 的計算速度快，且優(yōu)化程度隨著圖規(guī)模的增大而增大。多次重復實驗也同樣顯示此規(guī)律。

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

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

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

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

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

4.3.2 正則樹實驗數(shù)據(jù)分析

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

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

圖10 正則樹中不同出度的運行時間

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

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

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

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

圖12 正則樹同樣頂點規(guī)模下不同出度的運行時間

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

實驗表明：基于并行計算的Dijkstra 算法的優(yōu)化效果與非葉子節(jié)點的出度有關，但當出度較小時，效果并不明顯。

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

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

圖14 正則樹中不同深度的運行時間

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

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

4.4 算法推廣實驗

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

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

表5 柵格模型圖中兩種算法運行時間對比

多標號的Dijkstra串行和并行算法計算速率均高于傳統(tǒng)的Dijkstra，且使用并行計算速率更高?？梢妰?yōu)化算法在此現(xiàn)實場景中有較好的計算效率。

5 結(jié)束語

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

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