D ijkstra 算法的優(yōu)化

遇 娜,簡廣寧

(1.天津市紅橋區(qū)職工大學(xué),天津市 300131;2.天津城市建設(shè)學(xué)院,天津市 300384)

D ijkstra 算法的優(yōu)化

遇 娜1,簡廣寧2

(1.天津市紅橋區(qū)職工大學(xué),天津市 300131;2.天津城市建設(shè)學(xué)院,天津市 300384)

Dijkstra算法是許多工程解決最短路徑問題的理論基礎(chǔ),可用來找出圖中指定節(jié)點到其他節(jié)點的最短距離,有著廣泛的應(yīng)用。文章通過分析傳統(tǒng)Dijkstra算法的設(shè)計思想,提出該算法在實現(xiàn)方法上存在的一些不足之處,并從節(jié)約存儲空間和提高運算效率方面對其進(jìn)行了改進(jìn),并通過復(fù)雜性分析比較,得出這種改進(jìn)算法的效率優(yōu)于傳統(tǒng)的Dijkstra算法。

最短路徑 ;D ijkstra算法;鄰接表;堆排序

最短路徑問題是圖論研究中一個重要課題。傳統(tǒng)公認(rèn)的求最短路徑最好的算法是D ijkstra算法,它是由荷蘭著名的計算機科學(xué)家艾茲格·迪科斯徹提出來的,可用來找出圖中指定節(jié)點到其他節(jié)點的最短距離。其主要思想是從源點求出長度最短的一條路徑,然后通過對路徑長度迭代得到從源點到其他目標(biāo)節(jié)點的最短路徑。但隨著所解決問題規(guī)模的增大,應(yīng)用傳統(tǒng)的D ijkstra算法會使時間和空間復(fù)雜度不斷加大。因此,需對傳統(tǒng)的Dijkstra算法進(jìn)行了改進(jìn),提出采用鄰接表和堆排序的一種新的優(yōu)化方法。

一、傳統(tǒng)的D ijkstra算法

1.算法的基本思想

D ijkstra算法用于計算一個源節(jié)點到所有其他節(jié)點的最短代價路徑,它是按路徑長度遞增的次序來產(chǎn)生最短路徑的算法。下面以鄰接矩陣描述Dijkstra算法的實現(xiàn)過程。假設(shè)用帶權(quán)的鄰接矩陣Cost來表示具有N個結(jié)點的帶權(quán)有向圖G[3],Cost[i,j]表示弧的權(quán)值,如果從Vi到V j不通,則Cost[i,j]=∞。引進(jìn)一個輔助向量D ist并設(shè)VS為起始點,每個分量D ist[i]表示已找到的從起始點VS到每個終點Vi的最小權(quán)值。則該向量的初始值為:D ist[i]=Cost[S,i]V i∈V。其中,V是結(jié)點的集合。令S為已經(jīng)找到的從起點出發(fā)的最短路徑的終點集合,初始值為S={VS},則從VS出發(fā)到圖G上其它所有結(jié)點Vi可能達(dá)到的最短路徑長度為D ist[i]=Cost[S,i]V i∈V。

(1)選擇V j,使得D[j]=m in{D[i]|V i∈V-S}。V j就是當(dāng)前求得的一條從VS出發(fā)的最短路徑的終點,令S=S∪{V j}。

(2)修改從VS到集合V-S中任意一頂點V K的最短路徑長度。如果D[j]+Cost[j,k]

(3)修改D ist[k]為D isk[k]=D ist[j]+Cost[j,k];重復(fù)第2、3步操作共 N-1次,由此求得從VS到其他頂點的最優(yōu)路徑,該路徑是各權(quán)值遞增的序列。

2.算法分析

通過對該算法的仔細(xì)分析與研究可以得出,上述算法中有幾點不足之處:

(1)用鄰接矩陣Cost來存儲網(wǎng)絡(luò)圖,其存儲量為N×N。對于大型稀疏矩陣,這將耗費大量資源存儲那些無意義的矩陣元素。

(2)當(dāng)從未標(biāo)記節(jié)點集合(V-S)選定下一個節(jié)點V j作中間節(jié)點后,在更新操作過程中,需要掃描所有的未標(biāo)記節(jié)點并進(jìn)行比較更新。而未標(biāo)記節(jié)點集合(V-S)中往往包含大量與中間節(jié)點V j不直接相連的節(jié)點。

(3)在選擇下一個最短路徑節(jié)點作為中間節(jié)點時,需要比較所有的未標(biāo)記節(jié)點,而這個中間節(jié)點往往包含在與已標(biāo)記節(jié)點S集合的所有節(jié)點鄰接的節(jié)點中。

(4)在算法的每次迭代中,由于未標(biāo)記節(jié)點以無序的形式存放在一個鏈表中或一個數(shù)組中,每次選擇最短路徑節(jié)點都必須將所有未標(biāo)記節(jié)點掃描一遍,當(dāng)節(jié)點數(shù)目很大時,這無疑將成為制約計算速度的關(guān)鍵因素。

二、Dijkstra算法的優(yōu)化

針對Dijkstra算法存在的問題,我們在數(shù)據(jù)的組織和存儲以及最短路徑節(jié)點的選取上,進(jìn)行了改進(jìn)。

1.優(yōu)化思路分析

(1)數(shù)據(jù)組織和數(shù)據(jù)存儲

用鄰接矩陣存儲圖需要開辟N×N(N為節(jié)點數(shù)目)的存儲空間,對于一個大型稀疏圖來說,計算效率和存儲效率都很低。所以可以采用鄰接表來存儲網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以節(jié)省存儲空間。

(2)節(jié)點排序和最短路徑節(jié)點的選取

在改進(jìn)算法中,初始時,待排序的節(jié)點以無序形式連續(xù)序存放在一個一維數(shù)組中,對其進(jìn)行堆排序,調(diào)整成小頂堆后,各節(jié)點即是以完全二叉樹的順序存儲結(jié)構(gòu)形式存儲,0號單元存放的即是調(diào)整后的堆頂元素,后面依次以左子樹、右子樹。在調(diào)整堆的過程中時間復(fù)雜度為O(logN),(N為待排序節(jié)點個數(shù))。與從無序結(jié)構(gòu)下的數(shù)組或鏈表中選擇下一個最短路徑節(jié)點相比較,明顯地節(jié)約了時間,提高算法執(zhí)行效率。

2.改進(jìn)的Dijkstra算法基本思想

設(shè)置兩個集合S和adj及一個數(shù)組T[],S是已標(biāo)記集合,adj是鄰接點集,T[]存儲待排序節(jié)點。初始狀態(tài)時,S={V 0},T[]=adj[V 0],首先,將數(shù)組 T[]通過堆排序調(diào)整為小頂堆,取數(shù)組首元即堆頂節(jié)點current為中間節(jié)點,并將current加入到已標(biāo)記集合S中;再次,比較更新current的鄰接點集合與已標(biāo)記集合的差集(A dj[current]-S)中任一節(jié)點V i的當(dāng)前最短路徑值;然后查找S集合所有節(jié)點的鄰接點的并集與S集合的差集(∪adj[S])-S),同時將這些節(jié)點順次存入數(shù)組T中,覆蓋原數(shù)組中的節(jié)點,并設(shè)置一個計數(shù)器i記錄節(jié)點個數(shù);最后將數(shù)組中的前i個元素按它們當(dāng)前的最短路徑值調(diào)整成小頂堆,取堆頂節(jié)點為下一個最短路徑節(jié)點將其歸并到集合S中。如此反復(fù)迭代循環(huán),直到所有的節(jié)點都加入到集合S中。下面用Dijkstra算法求圖G中節(jié)點V 0到其它各節(jié)點的最短路徑D[V],圖G以鄰接表為存儲結(jié)構(gòu)。

三、復(fù)雜性分析與比較

1.空間復(fù)雜度分析

對于數(shù)據(jù)的存儲傳統(tǒng)的Dijkstra算法采用圖論中的鄰接矩陣方法,其存儲量為N×N(N為網(wǎng)絡(luò)圖中的節(jié)點數(shù)),通常的網(wǎng)絡(luò)圖盡管節(jié)點很多,但與節(jié)點相關(guān)聯(lián)的節(jié)點數(shù)目并不多,一般都為稀疏圖,這樣該存儲方法將浪費大量的空間,而且在計算時亦要花費大量的時間遍歷無意義的數(shù)據(jù)。而本文的改進(jìn)算法采用了鄰接表的鏈?zhǔn)酱鎯Y(jié)構(gòu),對于一個無向圖來說,其存儲量為O(E+2N)(E為節(jié)點列表中同節(jié)點關(guān)聯(lián)的所有弧段數(shù)目)。另外還使用了兩個數(shù)組,其中一個數(shù)組D[V]用來存儲所求得源點到其它所有節(jié)點的最短路徑值,另外一個數(shù)組 T[V]用來暫存待排序節(jié)點。所以總的空間復(fù)雜度為O(E+4N)。與傳統(tǒng)Dijkstra算法相比較,節(jié)省了空間,提高了存儲效率。

2.時間復(fù)雜度分析

傳統(tǒng)D ijkstra算法采用廣度優(yōu)先的搜索策略,在訪問了網(wǎng)絡(luò)中所有的節(jié)點后,最終生成從源點到其余各點的最短路徑樹。該算法在選擇最短路徑節(jié)點時需要訪問所有的未標(biāo)記節(jié)點,效率低下,整個算法的運行時間為O(N×N)。而改進(jìn)的Dijkstra算法而改進(jìn)算法的主要步驟查找待排序節(jié)點和堆排序上,因待排序節(jié)點為所有已標(biāo)記節(jié)點的鄰居節(jié)點的并集與標(biāo)記集合的差集(∪adj[S])-S),所以這個步驟的運行時間主要取決于已標(biāo)記節(jié)點的鄰節(jié)點集合元素數(shù)量的多少(而該數(shù)量值往往小于未標(biāo)記集合中的元素個數(shù)),查找次數(shù)最多為E次。在排序過程中,每次調(diào)整的時間復(fù)雜度不會超過滿二叉樹的高度logN。這兩個過程共需迭代執(zhí)行N次,因此整個算法理論上最長運行時間僅為O(N(logN+E))。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖具有的節(jié)點數(shù)N較大且其關(guān)聯(lián)矩陣為一個稀疏矩陣時,相對傳Di2 jkstra算法,優(yōu)化算法大大減少了計算次數(shù)與比較次數(shù),在一定程度上提高了運算速度。

四、結(jié)論

傳統(tǒng)D ijkstra算法使用的是鄰接矩陣來存儲網(wǎng)絡(luò)圖,存儲量為N×N,而使用鄰接表來存儲網(wǎng)絡(luò)數(shù)據(jù)信息,可使存儲空間減少至N量級。另外,利用堆排序來選擇最短路徑節(jié)點,只處理標(biāo)記節(jié)點的相鄰節(jié)點,從而大量減少了要計算的節(jié)點數(shù),最終使得算法的時間復(fù)雜度由原來的O(N 2)降至O(N(logN+E))。隨著網(wǎng)絡(luò)中節(jié)點數(shù)目和邊數(shù)的增多,這種改進(jìn)的Dijkstra算法越來越顯示出其優(yōu)勢,可使算法所需的時間明顯減少,并獲得精度較高的結(jié)果。

[1]王戰(zhàn)紅,孫明明,姚瑤.Dijkstra算法程序的優(yōu)化與實現(xiàn)[J].湖北第二師范學(xué)院學(xué)報2008,(08).

[2]李臣波.一種基于Dijkstra的最短路徑算法[J].哈爾濱理工大學(xué)學(xué)報2008,(13).

[3]杜興勇,劉延平,王忠文.Dijkstra算法程序的優(yōu)化與實現(xiàn)[J].通化師范學(xué)院學(xué)報,2008,(12).

A bs tra c t:Dijkstra algorithm is used to find the shortest path between various nodes at the right value in a given graph.In many p rojects it serves as the rationale for solving the shortest path p roblem.On the basis of an analysis of traditional Dijkstra algorithm’s design philosophy,the paper p resents some of its defects in imp lementation and puts forw ard some suggestions for imp rovement for the purpose of saving memory space and increasing efficiency.Furthermore,by comparison of their comp lexity analy2 sis,it p roves that the imp roved algorithm is superior to the traditional one in efficiency.

Key word s:shortest path;Dijkstra algorithm;adjacency list;heap sort

The Op tim ization of Dijkstra Algo rithm

YU Na1,JIAN Guang -ning2
(1.Tianjin Hongqiao District Staff and Workers University,Tianjin 300131 China;2.Tianjin U rban Construction Institute,Tianjin 300384 China)

TP312

A

1673-582X(2011)02-0089-03

2010-11-10

遇娜(1977-),女,天津市人,天津市紅橋區(qū)職工大學(xué)講師,從事計算機方面的教學(xué)與研究。