Dijkstra最短路徑算法的堆優化實驗研究

張翰林，關愛薇，傅 珂，孫廷凱

(1. 南京理工大學 理學院，江蘇 南京 210094；2. 南京理工大學 計算機科學與工程學院，江蘇 南京 210094)

Dijkstra最短路徑算法的堆優化實驗研究

張翰林1，關愛薇1，傅 珂1，孫廷凱2

(1. 南京理工大學 理學院，江蘇 南京 210094；2. 南京理工大學 計算機科學與工程學院，江蘇 南京 210094)

Dijkstra最短路徑算法是圖論的經典算法。設有向圖G有n個頂點和m條弧，則該算法的時間復雜度為Θ(m+n2)。前人的理論研究表明，若用二叉堆或d堆作為輔助數據結構，可不同程度地降低算法的時間復雜度。但是，這些研究給出的都是比較松弛的上界描述。本文設計了一系列實驗，利用二叉堆和d堆實現了該算法的優化，并通過模型擬合回歸的方式研究了優化算法的時間復雜度。我們發現，對于稠密圖，采用二叉堆優化算法，實際的時間復雜度可降低為m和nlogn的線性函數；而采用d堆，時間復雜度可降低為m、ndlogdn、nlogdn、dlogdn和n的線性函數，其中的d值對復雜度有顯著影響，變化趨勢呈現某些共同特征，而最優d值位于[5,7]區間。

Dijkstra最短路徑算法；二叉堆；d堆；時間復雜度

0 引言

1959年，狄克斯特拉（Edsgar Dijkstra）成功設計并實現了在有障礙物的兩個地點之間找出一條最短路徑的高效算法，這個算法被命名為“狄克斯特拉算法[1]”，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用[2-6]。

最短路徑不僅僅指地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、容量、線路等。歸結起來就是指由結點和路徑組成的圖中兩結點之間的最短路徑[7]。

最短路徑問題一直是運籌學、計算機科學、地理信息科學、交通運輸等領域的一個研究熱點[5-9]。很多實際問題都可以通過抽象進而轉化為網絡中的最短路徑計算問題，如道路交通網絡中的出行路線選取問題，計算機網絡中信息流在路由器間的最佳傳輸問題，以及社會關系網絡中兩個陌生人之間的聯系緊密度計算問題等。因此，針對網絡中最短路徑的有效計算問題研究具有重要的理論和現實意義。

近年來伴隨著大規模動態網絡數據的出現，最短路徑的實時計算面臨著新一輪的挑戰。很多實際系統（如GPS導航系統以及消防、救災等應急系統）都要求在盡可能短的時間內獲取最佳路徑，以更好地應對網絡動態等方面的影響，為用戶提供快速決策。所有這些都依賴于更高性能的最短路徑算法[6-9]。

堆是一種數據項按序排列的數據結構。在排序問題中[10-11]，堆結構具有優良的時間復雜度。d-堆則是堆（二叉堆）的一個變形[10-11]，比二叉堆更加靈活。如果用堆結構作為Dijkstra算法中的數據存儲結構，該算法的時間復雜度將被優化。

在Dijkstra算法中，設有向圖G有n個頂點和m條弧，使用鄰接表作為圖的存儲結構，則該算法的時間復雜度為Θ(m+n2)[11]。而在實際工程計算中，n通常較大，Θ(n2)的算法復雜度較高，有較大的提升空間。可以證明，若用最小堆作為輔助數據結構，算法的復雜度可降低為O( mlogn)[11]；若進一步用d堆（二分堆的推廣）結構，精心選擇合適的d值，對于稠密圖，算法的復雜度可降低到O( m)，即線性時間復雜度[11]。然而，上述理論分析得出的都是比較松弛的上界描述，實際上由于圖結構的復雜性，算法的實際性能尚未可知，本項目將對這個問題進行研究和實現。

1 理論基礎

1.1 傳統算法

先介紹Dijkstra傳統算法。

首先，我們有一個由節點和有向弧組成的有向圖G，該圖所有邊（弧）的權值均非負。開始，我們將所有的節點劃分為兩個集合X和Y。初始時，X ={1}, Y = {2,3,4,…,n}。若x∈X,則表示由源點到x節點的最短路徑已經被找到；Y則記錄了剩余的節點（最短路徑還沒有被確定的節點）。Y中的每個節點y有一個對應的量λ[y]，該值是從源節點到y (并且只經由X中的節點) 的最短路徑值。

Dijkstra算法[11]：

1. 假設V={1,2,3,…,n}表示所有節點，且源點為1，則X←{1}；Y←V-{1}。

2. 對于所有的y∈Y，若存在從1到y的邊，則令λ[y]等于這條邊的長度，否則令λ[y]=∞。

3. 選擇一個λ[y]最小的頂點y∈Y，并將其移動到X 中。

4. 將Y中每個和y相鄰的頂點w的λ[w]都重新計算并更新(表示經由y到w的一條更短的路徑被發現)。

5. 若Y≠?，則回到第二步，否則算法結束。

在上述算法中，所有的結點被分為三種類型，即已標記節點（即集合X中的節點）、未標記節點（即集合Y中那些λ[y]=∞的節點）和臨時標記節點（即集合Y中那些λ[y]為有限值的節點）。在上面的算法中，關鍵的是第3步，需要從臨時標記節點中尋找λ[y]最小的節點。若將這些節點的權值λ [y]保存在數組、鏈表或者隊列等線性結構中，每次查找最小值都需要用傳統的遍歷算法，則該步驟的時間復雜度為Θ(n2)。在第4步中，這個步驟恰好對每條邊都檢查一次，所以其時間復雜度為Θ(m)。因此該算法的時間復雜度為Θ(m+n2)，對于m＜nlogn的稀疏圖，或者對于m≥nlogn的稠密圖，算法的復雜度都可以表示為Θ(n2)。

1.2 二叉堆優化算法[11]

接下來介紹我們如何用堆（二叉堆）來優化Dijkstra算法。

1.2.1 堆優化動機

堆是一種特殊的完全二叉樹，其中小頂堆具有這樣的特點：父節點的鍵值不大于子節點的鍵值，堆的數組表示呈“基本有序”狀態，堆頂元素永遠是最小的。這樣的特性剛好能滿足這個算法的需求，所以，我們可以使用堆結構來優化Dijkstra算法。堆元素保存在形如H[1...n]的數組內，其中H[1]為堆的根。

1.2.2 堆排序算法在Dijkstra算法中的實現

先介紹上浮和下滲算法。

若某個節點H[i]鍵值小于其父節點的鍵值（或大于其兒子節點的鍵值），就違背了堆的特性，需要進行上浮（或下滲）調整。

調整方法為：

上浮：比較H[i]及其父節點H[i/2]的鍵值，若key(H[i])

下滲：沿著從H[i]到子節點(可能不唯一，則取其鍵值較小者)的路徑，比較H[i]與子節點的鍵值，若key(H[i])>min(H[2i], H[2i+1])則交換之。重復這一過程直到葉子節點或滿足堆特性為止。

在Dijkstra算法中，我們需要修改節點鍵值、插入節點和刪除節點這三種操作，他們均可用上浮和下滲兩種算法完成。

修改節點鍵值：直接修改，然后根據需要對該節點進行上浮操作直到滿足堆特性為止。

插入節點：將需插入的節點放在堆的最后一個位置，然后對該節點做上浮操作，直到滿足堆特性為止。

刪除堆頂節點：先用堆中最后一個節點取代H[1]，然后對H[1]作下滲操作，直到滿足堆特性為止。

1.2.3 堆排序算法在Dijkstra算法中的時間復雜度

1.3 d堆優化算法[11]

d-堆（有的文獻稱為k叉堆）是一種新型的數據結構，d-堆與普通堆很類似，普通堆即二叉堆，但d-堆中的每個非葉結點有d個子女，而不是2個。

由這個特性知，高度為h的一個滿的d叉堆的結點個數為dh-1；有n個元素的d叉堆高度為h=O(logdn)，即：每次上浮操作耗時為O(logdn)，下滲操作由于要和d個兒子進行比較，所以耗時為O( dlogdn)。如果我們用d-堆代替二叉堆來優化Dijkstra算法，顯然時間復雜度將降為O( ndlogdn+ mlogdn)[11]。

進一步，對于稠密圖(m≥n1+ε)，如果我們選取d的值為，那么時間復雜度將變為

這證明，對于稠密圖(m≥n1+ε)，d堆優化的Dijkstra算法可將其時間復雜度進一步降至O( m/ε)，即線性階。

2 擬合實驗

然而，這些堆優化分析得出的都是比較松弛的上界描述。在實際中，堆優化的效果究竟如何，優化后的算法復雜度是什么，還未可知。接下來，我們將用實驗來探究。

2.1 傳統算法

首先設計實驗數據。圖G須滿足稠密圖的條件，即頂點數n和邊數m滿足m≥nlogn。若取m=n1+（εε＞0），則當n比較小時，ε需要取得很大，才能從數值上滿足稠密圖的要求m≥nlog n，不利于實驗數據的選取。所以，我們取m=knlog（n k≥1），這樣配置的圖可以保證滿足稠密圖的要求m≥nlogn。然后，我們取頂點數n分別為32，64，128，256，400，512，700，900，1024。由于在圖G中，m存在上界，即m≤(n-1)n，所以當n=32時，k可取1,2,3,4,5,6；當n≥64時，可取k=1,2,3…10。對于每種配置的(n,m)，隨機生成10個有向圖，保存在鄰接表內。接下來的所有實驗中，我們將統一使用這組實驗數據，以便進行算法之間的對比。

在使用原始Dijkstra算法編寫的程序里加入計數器，分別記錄判斷、比較、賦值的次數。我們將使用判斷、比較和賦值次數之和S來作為算法時間復雜度的表征，即S=T(m,n)。對于對于每種配置的(n,m)，10個圖數據運行的結果進行平均得到T（ m, n）。記每個三元組(n, m, T( m, n))作為一組觀察數據。

實驗得到k組(n, m, T( m, n))數據，建立用m,n(和/或其對數形式)構造的多項式，例如T( m, n)= c n2+c n+c m+c的形式。假設我們找到一組參數

1234

ci,i=1,…4，我們希望對于每個參數配置(n,m)，這個模型擬合得到的值恰好等于觀察值T（ m, n），即可以表示為形如Ax=b的線性方程組，其中：一般來說k>>4，例如這里k=9，得到的超定方程組Ax=b一般沒有嚴格的代數解，為此我們使用最小二乘法，使得誤差平方Ax-b2盡量小。在Matlab中，這樣的解x?可以直接用x?=A b來計算。我們就可以構建根據需要構建各種不同的多項式模型，得到不同的參數向量解x，然后通過一定的評價方法對比研究這些模型的優劣（詳見下文描述）。

我們以n2作為最高次項，運用Matlab對若干模型進行擬合，得到各項系數，并計算各模型的絕對誤差和相對誤差，對比得到相對較優的模型，最后分析結果。

從結果數據來看，原始算法的操作總數S主要受圖的頂點數n影響，呈現二次函數關系，而與m的關系較小。

從回歸分析的結果來看，無論是哪種以n2作為最高次項模型，擬合精度都非常高，絕對誤差和相對誤差都極小，各項系數大小也貼近實際，非常合理。斟酌之后，我們選擇

S=1.5003n2+8.9329n+2.0028m+9.6572

作為最終的擬合模型。這個擬合結果與實際值的相對誤差的絕對值，用平均值和均方差來表示就是0.00160±0.00325。其三維圖像如圖1所示：

圖1 傳統算法復雜度函數三維圖Fig.1 Complexity Function of Traditional Algorithm 3-D Image

這是一個與理論分析完全一致的結果。這就驗證了原始的Dijkstra算法的時間復雜度為O( n2)。

2.2 二叉堆優化算法

我們改寫程序得到用二叉堆優化的Dijkstra算法程序，仍用相同的實驗數據，用同樣的方法運行程序，得到操作總數并繪制成表。

這次，我們將使用系統的誤差分析方法，綜合各個擬合模型的經驗風險、推廣性風險以及模型的復雜性來挑選合適的擬合模型。為了考察模型的泛化能力，對于每種配置(n,m)，我們又隨機生成了相同配置的另外10組圖，用于測試模型的推廣誤差，把原先的實驗結果稱為b1，推廣實驗的結果稱為b2，擬合模型的計算結果稱為b?=Ax，那么經驗誤差是推廣誤差就是，一般情況下，我們用r1+λr2來衡量一個模型擬合的好壞，其中正則化參數λ代表推廣誤差和經驗誤差重要程度的比值，在本實驗中，λ可取為1。我們還將模型的復雜程度作為一個標準，即在誤差r1+λr2相當的情況下，挑選那些相對更簡單光滑（即項數少、系數絕對值小）的模型作為最佳擬合模型。

我們以mlogn為最高次項，構建了可能包括nlogn、logn、m、n和常數項中的一項或若干項共25=32種所有形態的多項式模型，并進行最小二乘法擬合，計算和記錄各擬合模型的經驗誤差和推廣誤差，分析結果數據，得到以下結論（由于表格過大，數據略）：

二叉堆優化的Dijkstra算法的操作總數比起傳統的算法要小很多，這證明二叉堆的存儲結構確實優化了算法。從擬合結果的系數來看，最高次項mlog n前的系數并不統一，差別較大，對此我們得不到一個較好的結論。但如果從誤差的角度來分析，我們觀察若干個擬合精度較高的模型，它們有幾個共同特點：最高次項mlogn前面的系數絕對值都非常接近于0，有正有負；均包含m項和nlogn項，而且m項和nlogn項前面的系數都很穩定。在這組實驗中，我們根據擬合精度和模型復雜程度挑選出兩個最優的模型來作比對（見表1的1、2號模型）。

于是我們考慮剔除mlogn這個“最高次項”，把m作為最高次項，考察了共24=16種形態的多項式，進行重新擬合。觀察擬合結果，我們發現，擬合模型只要含有m項和nlogn項，就能得到誤差小，系數穩定的擬合結果。我們同樣擇優選出兩個模型來作比較（見表1的3、4號模型）。

表1 二叉堆優化算法模型比較Tab.l Binary Heap Optimization Algorithm Model Comparison Table

從此表中可以得出一個顯而易見的結論：mlog n是一個可有可無的項，m和nlogn才是這個算法的最高次項。

綜合經驗誤差與推廣誤差，同時為了追求模型的簡單，我們選擇3號模型。

S=3.0476m+4.721nlogn

作為最終的擬合模型，其三維圖像如圖2所示：

圖2 二叉堆優化算法函數圖像Fig.2 Binary Heap Optimization Algorithm Function Image

我們可以說，二叉堆優化的Dijkstra算法的時間復雜度實際上已經達到了用斐波那契堆進行優化的復雜度[9](log)

O mnn+，實驗可以佐證這一點。

對于這一現象，可以做出如下解釋：

1. 首先，在這個算法中，如我們前面所說，插入堆操作共有(n-1)次，這個數字就是算法實際上執行的次數；更新操作最多有(m-n+1)次，但在實際的操作中，會有很多無需更新節點權值的時候（即新的權值大于當前權值），更新操作的實際執行次數遠遠達不到(m-n+1)這個上限。

2. 堆操作的時間復雜度被認為是(log)On。但實際上，堆的初始大小僅為源點s的鄰接點個數，算法執行過程中，每次選中一個新的臨時標記結點，伴隨著每次刪除堆頂元素，可能有若干新的臨時標記結點插入堆（具體跟圖的連接結構有關），但堆中的節點個數從不會達到n個，堆高實際上可能小于甚至遠小于O(logn)，直至堆空，算法結束。因此O(logn)是堆高度上界的松弛描述，實際上可能遠遠低于這個量級，這造成了實際上的時間復雜度遠低于理論上的時間復雜度。

綜上，二叉堆優化的Dijkstra算法的時間復雜度實際上是：

而且這是一個非常松弛的上界，我們即使用實驗得到他的時間復雜度為m的線性階也不奇怪。不過接下來的這個巧妙的堆結構，能夠從理論上把該算法的時間復雜度降為m的線性階。

2.3 d堆優化算法

2.3.1 d堆優化算法的時間復雜度研究

首先我們對一般的d堆進行研究。我們改寫程序得到用d堆優化的Dijkstra算法程序，然后設置d值為一般值——d取遍從5到15的所有值，再用前述同樣的圖數據輸入d堆優化算法，用同樣的方法處理實驗結果。我們先以mlogdn和ndlogdn為最高次項，構建了可能包括nlogdn、dlogdn、logdn、m、n和常數項中的一項或若干項共26=64種所有形態的多項式模型，并進行最小二乘法擬合，將擬合結果匯成表格（同上，數據略），得到了同二叉堆類似的現象——最高次項mlogdn前的系數不統一，不穩定；而m項前的系數最為穩定，而且是否包含m項與模型的精準程度有著很大的相關性。我們綜合誤差與模型的復雜程度，選擇出了兩組相對比較好的模型（見表2的1、2號模型）。

同樣我們去除最高次項mlogdn再一次擬合，考察了64種多項式模型，觀察擬合結果，發現與前一次實驗類似，擬合模型只要含有m項和nlogdn項，就能得到很好的擬合結果。這說明，mlogdn這一項對擬合精度影響很小。我們擇優挑選出了3組擬合結果（見表2的3、4、5號模型）。

表2 d堆優化算法模型比較Tab.2 Binary Heap Optimization Algorithm Model Comparison Table

接下來我們嘗試將ndlogdn這一項也去除，繼續考察了64種多項式模型，作為對比試驗，發現這次的擬合結果誤差均不如人意，最好的模型其誤差也超出其他組實驗誤差幾倍之多。我們能夠得出結論：ndlogdn是不可或缺的一項。

表2列出了以上每次選擇所得到的較優的模型及其參數。

綜合經驗誤差、推廣誤差、模型的復雜程度等多方面因素，我們選擇5號模型。

作為最終的擬合結果。取其最高階，可以認為：算法的復雜度被優化為Θ(m+ndlogdn)。

選擇d=10時，其三維圖像如圖3所示：

圖3 d堆優化算法函數圖像(d=10)Fig.3 D-heap Optimization Algorithm Function Image(d=10)

這就證明，d堆優化的Dijkstra算法的時間復雜度已經達到了()O m。

2.3.2 d堆優化算法中關于d值的研究

在單純的堆排序算法中，我們把d堆與二叉堆相比，不難證明，當d為e附近（即d=3）時，堆排序的時間性能可達到最優。在利用d堆作為存儲結構的Dijkstra算法中，具體情況與單純的堆排序算法有所不同，但我們容易知道，它也存在一個最優的d值，使該算法的時間復雜度達到最低。

在理論的證明中，我們令d=2+/m n，能夠證明d堆優化算法的時間復雜度能夠達到線性階[11]，但它并不是最優的d值。現在，我們想研究d為何值時，該算法方能達到最佳的優化效果。

我們令d從2取到40，對原數據進行大量的實驗。限于篇幅，圖4展示了部分結果。

圖4 S-d關系圖Fig.4 S-d relation Image

從圖中可看出，每一條曲線都有一個最低值。在d從2開始增大時，操作總數S先是迅速降低，然后緩緩降低至最低值；然后又緩緩回升，并隨著d的增大呈現穩定增長的趨勢。曲線在最低值兩側的附近波動較小，形成一個小區間，我們可以認為最優的d值落在一個區間里。在這個區間的兩側，曲線都表現出明顯的單調性。

從理論的角度來分析，開始操作總數S隨著d值的增大而迅速降低，其原因是d堆的存儲結構有效得降低了堆的高度，因為堆的高度logdn隨著d的增大而減小。而當d值達到最優值之后，操作總數S隨著d值的增大而增大，是因為在執行下滲操作時，節點要同時與d個兒子相比較，其時間復雜度為O( dlogdn)，當d達到某個值的時候，下滲算法的時間復雜度會隨著d的增大而增大，這也導致了整個算法時間復雜度的增大。

就我們所展示的這4種配置的圖而言，它們的最優d值分別為6、6、7、5，而它們2+m/ n的值分別為14、42、47、42，這結果顯示，使算法時間成本最低的d值與m、n并無關聯，而是在一個比較穩定的范圍內小幅波動——即d∈[5,7]。

如果我們把傳統算法、二叉堆優化算法、d堆優化算法的結果畫在同一張圖中（圖略），就能夠明顯得看出，以二叉堆作為存儲結構，能夠極大地優化Dijkstra算法，假如用d堆作為存儲結構，選擇合適的d值，該算法還能被進一步優化。

3 小結

本文設計了一系列實驗，研究了最短路徑算法及其堆優化算法，得到如下結論：

1. 驗證了Dijkstra傳統算法的時間復雜度是Θ(n2)階的。

2. 二叉堆優化的Dijkstra算法的時間復雜度可從理論上證明出是O( mlogn)階，但實驗可證明，對于稠密圖，算法的時間復雜度可以用m和nlogn的線性函數表示。

3. 采用d堆優化，時間復雜度可降低為m、ndlogdn、nlogdn、dlogdn和n的線性函數。

4. d堆優化算法的參數d對復雜度有顯著影響，變化趨勢呈現某些共同特征，最優d值位于[5,7]區間。

該問題的實驗研究可能會為另一個貪心算法--最小生成樹的Prim算法的研究[13-15]帶來一些新的啟示。另外，理論會給我們提供正確的標尺和方向，而實驗會帶領我們踏上真理的大陸。所以，不滿足于理論，勤于用實驗去檢驗，才能不斷地有新的發現。

[1] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerical Mathematics, 1959, 1(1): 269-271.

[2] Wang Shu-Xi, The Improved Dijkstra's Shortest Path Algorithm and Its Application[C]. Procedia Engineering, 2012, 29: 1186–1190.

[3] Jayadev Misra. A walk over the shortest path: Dijkstra’s Algorithm viewed as fi xed-point computation[J]. Information Processing Letters, 2001, 77(2): 197–200.

[4] Domenico Cantone, Simone Faro.Two-Levels-Greedy: a generalization of Dijkstra’s shortest path algorithm[J]. Electronic Notes in Discrete Mathematics, 2004, 17(10): 81–86.

[5] 賀凱, 李韶杰, 吉亞威, 等. 移動機器人新型半智能路徑導航系統的設計與實現[J]. 軟件, 2013, 34(4): 1-6.

[6] 徐彬, 王權鋒, 劉斌, 等. 貪婪和A-Star算法在物流配送中的應用及仿真[J]. 軟件, 2013, 34(6): 35-39.

[7] 樂陽, 龔健雅. Dijkstra 最短路徑算法的一種高效率實現[J]. 武漢測繪科技大學學報, 1999, 24(3): 209-212.

[8] 嚴寒冰, 劉迎春. 基于GIS的城市道路網最短路徑算法探討[J]. 計算機學報, 2000, 23(2): 210-215.

[9] 宋青, 汪小帆. 最短路徑算法加速技術研究綜述[J].電子科技大學學報, 2012, 41(2): 176-184.

[10] T.H. Corman等, 算法導論(第三版)[M]. 潘金貴等譯, 北京:機械工業出版社, 2013.

[11] M.H. Alsuwaiyel, 算法設計技巧與分析[M]. 吳偉昶等譯,北京: 電子工業出版社, 2010.

[12] E. Horowitz, 數據結構基礎(C語言版, 第二版)[M]. 北京:清華大學出版社, 2009.

[13] 嚴蔚敏, 吳偉民. 數據結構(C語言版)[M]. 北京: 清華大學出版社, 2002.

[14] C.F. Bazlamac, Khalil S. Hindi, Minimum-weight spanning tree algorithms: A survey and empirical study[J], Computers & Operations Research, 2001, 28(8): 767-785.

[15] 李光杰, 王聰. 基于偏序堆的Prim 算法設計與實現[J]. 軟件, 2014, 35(2): 67-69.

Experimental Study of Heap Optimization of Dijkstra Shortest Path Algorithm

ZHANG Han-lin1, GUAN Ai-wei1, FU Ke1, SUN Ting-kai2
(1. Nanjing University of Science and Technology, School of Science NJUST, Nanjing Jiangsu 210094; 2. Nanjing University of Science and Technology, School of Computer Science and Engineering, Nanjing Jiangsu 210094)

Dijkstra shortest path algorithm is a classical algorithm of graph theory.Given graph G with n vertices and m arcs, the time complexity of this algorithm is Θ(m+n2).The predecessors' theoretical research shows that if the binary heap or d-heap is used as the auxiliary data structure, the time complexity of the algorithm can be reduced to varying degrees.However, what these previous studies have given is relatively relaxed upper bounds.In this paper, we design a series of experiments, using binary heap and d-heap to realize the optimization of the algorithm, and through the method of model fitting and regression to study the time complexity of the optimized algorithms.We find that for the dense graph, using the binary heap, the actual time complexity can be reduced to the linear function of m and nlogn; and using the d-heap, the time complexity can be reduced to the linear function of m, ndlogdn, nlogdn, dlogdnand n. Moreover, the value of d has a significant impact on the complexity in terms of some common varying characteristics, and the optimal value of d is located at [5,7].

Dijkstra shortest path algorithm; Binary heap; D-heap; Time complexity

TP301.5

A

10.3969/j.issn.1003-6970.2017.05.004

南京理工大學江蘇省級大學生科研創新訓練項目“Dijkstra最短路徑算法的堆優化研究”

張翰林，男，1995--，本科生，主要研究方向：信息與計算科學；關愛薇，女，1995--，本科生，主要研究方向：信息與計算科學；傅珂，女，1995--，本科生，主要研究方向：信息與計算科學；孫廷凱(本文通訊作者)，男，1975--，副教授，主要研究方向。

本文著錄格式：張翰林，關愛薇，傅珂，等. Dijkstra最短路徑算法的堆優化實驗研究[J]. 軟件，2017，38（5）：15-21