遇 娜,簡(jiǎn)廣寧

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

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

遇 娜1,簡(jiǎn)廣寧2

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

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

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

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

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

1.算法的基本思想

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

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

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

2.算法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、結(jié)論

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

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

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

[3]杜興勇,劉延平,王忠文.Dijkstra算法程序的優(yōu)化與實(shí)現(xiàn)[J].通化師范學(xué)院學(xué)報(bào),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é)講師,從事計(jì)算機(jī)方面的教學(xué)與研究。