張翰林，關(guān)愛薇，傅 珂，孫廷凱

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

Dijkstra最短路徑算法的堆優(yōu)化實(shí)驗(yàn)研究

張翰林1，關(guān)愛薇1，傅 珂1，孫廷凱2

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

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

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

0 引言

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

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

最短路徑問題一直是運(yùn)籌學(xué)、計算機(jī)科學(xué)、地理信息科學(xué)、交通運(yùn)輸?shù)阮I(lǐng)域的一個研究熱點(diǎn)[5-9]。很多實(shí)際問題都可以通過抽象進(jìn)而轉(zhuǎn)化為網(wǎng)絡(luò)中的最短路徑計算問題，如道路交通網(wǎng)絡(luò)中的出行路線選取問題，計算機(jī)網(wǎng)絡(luò)中信息流在路由器間的最佳傳輸問題，以及社會關(guān)系網(wǎng)絡(luò)中兩個陌生人之間的聯(lián)系緊密度計算問題等。因此，針對網(wǎng)絡(luò)中最短路徑的有效計算問題研究具有重要的理論和現(xiàn)實(shí)意義。

近年來伴隨著大規(guī)模動態(tài)網(wǎng)絡(luò)數(shù)據(jù)的出現(xiàn)，最短路徑的實(shí)時計算面臨著新一輪的挑戰(zhàn)。很多實(shí)際系統(tǒng)（如GPS導(dǎo)航系統(tǒng)以及消防、救災(zāi)等應(yīng)急系統(tǒng)）都要求在盡可能短的時間內(nèi)獲取最佳路徑，以更好地應(yīng)對網(wǎng)絡(luò)動態(tài)等方面的影響，為用戶提供快速決策。所有這些都依賴于更高性能的最短路徑算法[6-9]。

堆是一種數(shù)據(jù)項(xiàng)按序排列的數(shù)據(jù)結(jié)構(gòu)。在排序問題中[10-11]，堆結(jié)構(gòu)具有優(yōu)良的時間復(fù)雜度。d-堆則是堆（二叉堆）的一個變形[10-11]，比二叉堆更加靈活。如果用堆結(jié)構(gòu)作為Dijkstra算法中的數(shù)據(jù)存儲結(jié)構(gòu)，該算法的時間復(fù)雜度將被優(yōu)化。

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

1 理論基礎(chǔ)

1.1 傳統(tǒng)算法

先介紹Dijkstra傳統(tǒng)算法。

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

Dijkstra算法[11]：

1. 假設(shè)V={1,2,3,…,n}表示所有節(jié)點(diǎn)，且源點(diǎn)為1，則X←{1}；Y←V-{1}。

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

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

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

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

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

1.2 二叉堆優(yōu)化算法[11]

接下來介紹我們?nèi)绾斡枚眩ǘ娑眩﹣韮?yōu)化Dijkstra算法。

1.2.1 堆優(yōu)化動機(jī)

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

1.2.2 堆排序算法在Dijkstra算法中的實(shí)現(xiàn)

先介紹上浮和下滲算法。

若某個節(jié)點(diǎn)H[i]鍵值小于其父節(jié)點(diǎn)的鍵值（或大于其兒子節(jié)點(diǎn)的鍵值），就違背了堆的特性，需要進(jìn)行上?。ɑ蛳聺B）調(diào)整。

調(diào)整方法為：

上?。罕容^H[i]及其父節(jié)點(diǎn)H[i/2]的鍵值，若key(H[i])

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

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

修改節(jié)點(diǎn)鍵值：直接修改，然后根據(jù)需要對該節(jié)點(diǎn)進(jìn)行上浮操作直到滿足堆特性為止。

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

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

1.2.3 堆排序算法在Dijkstra算法中的時間復(fù)雜度

1.3 d堆優(yōu)化算法[11]

d-堆（有的文獻(xiàn)稱為k叉堆）是一種新型的數(shù)據(jù)結(jié)構(gòu)，d-堆與普通堆很類似，普通堆即二叉堆，但d-堆中的每個非葉結(jié)點(diǎn)有d個子女，而不是2個。

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

進(jìn)一步，對于稠密圖(m≥n1+ε)，如果我們選取d的值為，那么時間復(fù)雜度將變?yōu)?/p>

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

2 擬合實(shí)驗(yàn)

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

2.1 傳統(tǒng)算法

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

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

實(shí)驗(yàn)得到k組(n, m, T( m, n))數(shù)據(jù)，建立用m,n(和/或其對數(shù)形式)構(gòu)造的多項(xiàng)式，例如T( m, n)= c n2+c n+c m+c的形式。假設(shè)我們找到一組參數(shù)

1234

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

我們以n2作為最高次項(xiàng)，運(yùn)用Matlab對若干模型進(jìn)行擬合，得到各項(xiàng)系數(shù)，并計算各模型的絕對誤差和相對誤差，對比得到相對較優(yōu)的模型，最后分析結(jié)果。

從結(jié)果數(shù)據(jù)來看，原始算法的操作總數(shù)S主要受圖的頂點(diǎn)數(shù)n影響，呈現(xiàn)二次函數(shù)關(guān)系，而與m的關(guān)系較小。

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

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

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

圖1 傳統(tǒng)算法復(fù)雜度函數(shù)三維圖Fig.1 Complexity Function of Traditional Algorithm 3-D Image

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

2.2 二叉堆優(yōu)化算法

我們改寫程序得到用二叉堆優(yōu)化的Dijkstra算法程序，仍用相同的實(shí)驗(yàn)數(shù)據(jù)，用同樣的方法運(yùn)行程序，得到操作總數(shù)并繪制成表。

這次，我們將使用系統(tǒng)的誤差分析方法，綜合各個擬合模型的經(jīng)驗(yàn)風(fēng)險、推廣性風(fēng)險以及模型的復(fù)雜性來挑選合適的擬合模型。為了考察模型的泛化能力，對于每種配置(n,m)，我們又隨機(jī)生成了相同配置的另外10組圖，用于測試模型的推廣誤差，把原先的實(shí)驗(yàn)結(jié)果稱為b1，推廣實(shí)驗(yàn)的結(jié)果稱為b2，擬合模型的計算結(jié)果稱為b?=Ax，那么經(jīng)驗(yàn)誤差是推廣誤差就是，一般情況下，我們用r1+λr2來衡量一個模型擬合的好壞，其中正則化參數(shù)λ代表推廣誤差和經(jīng)驗(yàn)誤差重要程度的比值，在本實(shí)驗(yàn)中，λ可取為1。我們還將模型的復(fù)雜程度作為一個標(biāo)準(zhǔn)，即在誤差r1+λr2相當(dāng)?shù)那闆r下，挑選那些相對更簡單光滑（即項(xiàng)數(shù)少、系數(shù)絕對值?。┑哪Ｐ妥鳛樽罴褦M合模型。

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

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

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

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

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

綜合經(jīng)驗(yàn)誤差與推廣誤差，同時為了追求模型的簡單，我們選擇3號模型。

S=3.0476m+4.721nlogn

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

圖2 二叉堆優(yōu)化算法函數(shù)圖像Fig.2 Binary Heap Optimization Algorithm Function Image

我們可以說，二叉堆優(yōu)化的Dijkstra算法的時間復(fù)雜度實(shí)際上已經(jīng)達(dá)到了用斐波那契堆進(jìn)行優(yōu)化的復(fù)雜度[9](log)

O mnn+，實(shí)驗(yàn)可以佐證這一點(diǎn)。

對于這一現(xiàn)象，可以做出如下解釋：

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

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

綜上，二叉堆優(yōu)化的Dijkstra算法的時間復(fù)雜度實(shí)際上是：

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

2.3 d堆優(yōu)化算法

2.3.1 d堆優(yōu)化算法的時間復(fù)雜度研究

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

同樣我們?nèi)コ罡叽雾?xiàng)mlogdn再一次擬合，考察了64種多項(xiàng)式模型，觀察擬合結(jié)果，發(fā)現(xiàn)與前一次實(shí)驗(yàn)類似，擬合模型只要含有m項(xiàng)和nlogdn項(xiàng)，就能得到很好的擬合結(jié)果。這說明，mlogdn這一項(xiàng)對擬合精度影響很小。我們擇優(yōu)挑選出了3組擬合結(jié)果（見表2的3、4、5號模型）。

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

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

表2列出了以上每次選擇所得到的較優(yōu)的模型及其參數(shù)。

綜合經(jīng)驗(yàn)誤差、推廣誤差、模型的復(fù)雜程度等多方面因素，我們選擇5號模型。

作為最終的擬合結(jié)果。取其最高階，可以認(rèn)為：算法的復(fù)雜度被優(yōu)化為Θ(m+ndlogdn)。

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

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

這就證明，d堆優(yōu)化的Dijkstra算法的時間復(fù)雜度已經(jīng)達(dá)到了()O m。

2.3.2 d堆優(yōu)化算法中關(guān)于d值的研究

在單純的堆排序算法中，我們把d堆與二叉堆相比，不難證明，當(dāng)d為e附近（即d=3）時，堆排序的時間性能可達(dá)到最優(yōu)。在利用d堆作為存儲結(jié)構(gòu)的Dijkstra算法中，具體情況與單純的堆排序算法有所不同，但我們?nèi)菀字?，它也存在一個最優(yōu)的d值，使該算法的時間復(fù)雜度達(dá)到最低。

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

我們令d從2取到40，對原數(shù)據(jù)進(jìn)行大量的實(shí)驗(yàn)。限于篇幅，圖4展示了部分結(jié)果。

圖4 S-d關(guān)系圖Fig.4 S-d relation Image

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

從理論的角度來分析，開始操作總數(shù)S隨著d值的增大而迅速降低，其原因是d堆的存儲結(jié)構(gòu)有效得降低了堆的高度，因?yàn)槎训母叨萳ogdn隨著d的增大而減小。而當(dāng)d值達(dá)到最優(yōu)值之后，操作總數(shù)S隨著d值的增大而增大，是因?yàn)樵趫?zhí)行下滲操作時，節(jié)點(diǎn)要同時與d個兒子相比較，其時間復(fù)雜度為O( dlogdn)，當(dāng)d達(dá)到某個值的時候，下滲算法的時間復(fù)雜度會隨著d的增大而增大，這也導(dǎo)致了整個算法時間復(fù)雜度的增大。

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

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

3 小結(jié)

本文設(shè)計了一系列實(shí)驗(yàn)，研究了最短路徑算法及其堆優(yōu)化算法，得到如下結(jié)論：

1. 驗(yàn)證了Dijkstra傳統(tǒng)算法的時間復(fù)雜度是Θ(n2)階的。

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

3. 采用d堆優(yōu)化，時間復(fù)雜度可降低為m、ndlogdn、nlogdn、dlogdn和n的線性函數(shù)。

4. d堆優(yōu)化算法的參數(shù)d對復(fù)雜度有顯著影響，變化趨勢呈現(xiàn)某些共同特征，最優(yōu)d值位于[5,7]區(qū)間。

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

[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ī)器人新型半智能路徑導(dǎo)航系統(tǒng)的設(shè)計與實(shí)現(xiàn)[J]. 軟件, 2013, 34(4): 1-6.

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

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

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

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

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

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

[12] E. Horowitz, 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(C語言版, 第二版)[M]. 北京:清華大學(xué)出版社, 2009.

[13] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京: 清華大學(xué)出版社, 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 算法設(shè)計與實(shí)現(xiàn)[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

南京理工大學(xué)江蘇省級大學(xué)生科研創(chuàng)新訓(xùn)練項(xiàng)目“Dijkstra最短路徑算法的堆優(yōu)化研究”

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

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