基于Dijkstra的最短路徑問(wèn)題的算法分析與優(yōu)化

劉朝霞

（集寧師范學(xué)院數(shù)學(xué)系 內(nèi)蒙古集寧 012000）

基于Dijkstra的最短路徑問(wèn)題的算法分析與優(yōu)化

劉朝霞

（集寧師范學(xué)院數(shù)學(xué)系 內(nèi)蒙古集寧 012000）

Dijkstra算法是最具有代表性的最短路徑算法，為解決許多工程領(lǐng)域中出現(xiàn)的最短路徑問(wèn)題提供了理論依據(jù)。本文分析了Dijkstra算法以及該算法存在的不足，并提出了優(yōu)化該算法的方法，通過(guò)與原算法作比較，結(jié)果表明這種改進(jìn)的算法在運(yùn)行時(shí)間和效率上得到了提高，其占用的存儲(chǔ)空間得到了減少。

圖論；Dijkstra算法；最短路徑

最短路徑問(wèn)題是圖論中最經(jīng)典的問(wèn)題之一，在許多工業(yè)部門(mén)和實(shí)際工作中得到了很好的應(yīng)用。該算法主要用于計(jì)算從源點(diǎn)到其它各個(gè)頂點(diǎn)的所經(jīng)過(guò)的邊的總權(quán)和最小的路徑(最短路徑)，如在解決城市之間的最短鐵路(公路)問(wèn)題、管道鋪設(shè)以及設(shè)備更新和選址等實(shí)際問(wèn)題時(shí)，只需建立起相對(duì)應(yīng)的賦權(quán)圖，將實(shí)際問(wèn)題轉(zhuǎn)化為最短路徑問(wèn)題，通過(guò)Dijkstra算法即可求得最短路徑。這里的“最短路徑”遠(yuǎn)遠(yuǎn)超出了它的直觀意義，既指距離上的最短，又可引申為經(jīng)濟(jì)費(fèi)用、時(shí)間、吞吐量等廣義上的最短[1]。

一、最短路徑問(wèn)題以及Dijkstra算法原理

(一)最短路徑問(wèn)題

(二)Dijkstra算法思想及其步驟

1.Dijkstra算法思想

Dijkstra算法是一種貪心算法，它采用標(biāo)記法按各個(gè)頂點(diǎn)與源點(diǎn)之間的路徑長(zhǎng)度的遞增次序，先求出長(zhǎng)度最短的一條路徑，利用路徑長(zhǎng)度迭代的方法逐漸求出從源點(diǎn)到其它各個(gè)頂點(diǎn)的最短路徑[2]。

其基本思想是：將頂點(diǎn)集合分為僅含源點(diǎn)的標(biāo)記集合S和未標(biāo)記頂點(diǎn)集合V-S，其中集合S中的頂點(diǎn)當(dāng)且僅當(dāng)?shù)皆袋c(diǎn)的最短路徑長(zhǎng)度已確定，集合V-S中的頂點(diǎn)到源點(diǎn)的最短路徑長(zhǎng)度待定。設(shè),把從源點(diǎn)出發(fā)且中間只經(jīng)過(guò)S中的點(diǎn)到達(dá)u點(diǎn)的路徑稱為特殊路徑，并用數(shù)組dist記錄從源點(diǎn)到其它頂點(diǎn)的最短路徑的長(zhǎng)度[3]。Dijkstra算法每次不斷地從V-S集合中按照貪心策略搜索具有最短特殊路徑長(zhǎng)度的頂點(diǎn)u，將頂點(diǎn)u加入集合S來(lái)擴(kuò)充這個(gè)集合，同時(shí)修改數(shù)組dist的值。直到S=V時(shí)搜索結(jié)束，數(shù)組dist記錄了從源點(diǎn)到其它各個(gè)頂點(diǎn)的全部最短路徑。

2.Dijkstra算法的步驟

采用圖論中帶權(quán)圖的鄰接矩陣C來(lái)存儲(chǔ)圖中的頂點(diǎn)及各邊權(quán)值的數(shù)據(jù)信息，若，令上的權(quán)值，否則

二、Dijkstra算法分析

(1)使用帶權(quán)鄰接矩陣作為數(shù)據(jù)結(jié)構(gòu)來(lái)表示具有n個(gè)頂點(diǎn)的圖時(shí)，需定義存儲(chǔ)量為(其中N為節(jié)點(diǎn)數(shù))的鄰接矩陣。這樣，會(huì)產(chǎn)生兩個(gè)問(wèn)題：第一，當(dāng)圖的節(jié)點(diǎn)數(shù)較大時(shí)，需占用較大的計(jì)算機(jī)存儲(chǔ)空間；第二，對(duì)于大型的稀疏鄰接矩陣，將會(huì)占用大量計(jì)算機(jī)空間存儲(chǔ)稀疏矩陣中的無(wú)意義的0元素。

(2)頂點(diǎn)的搜索范圍較大，影響算法的運(yùn)行效率。初始化時(shí)，將圖中所有頂點(diǎn)除源點(diǎn)外都設(shè)置為未標(biāo)記頂點(diǎn)，在搜索過(guò)程中每次都要從未標(biāo)記頂點(diǎn)集合V-S中選擇與最短路徑頂點(diǎn)相鄰的頂點(diǎn)作為中間頂點(diǎn)，再?gòu)闹虚g頂點(diǎn)中選擇與源點(diǎn)具有最短路徑的頂點(diǎn)加入到標(biāo)記頂點(diǎn)集S中。在選擇中間頂點(diǎn)的過(guò)程中，每一次都要從V-S集合中掃描所有未標(biāo)記頂點(diǎn)并進(jìn)行比較更新，頂點(diǎn)的搜索范圍大，對(duì)中間節(jié)點(diǎn)的遍歷會(huì)造成算法瓶頸，影響算法執(zhí)行的效率。

三、Dijkstra算法優(yōu)化分析

針對(duì)Dijkstra算法中存在的不足，通過(guò)改進(jìn)數(shù)據(jù)結(jié)構(gòu)和縮小最短路徑頂點(diǎn)的搜索范圍的方法減少占用的存儲(chǔ)空間和算法的運(yùn)行時(shí)間，達(dá)到對(duì)算法進(jìn)行優(yōu)化的目的。

(1)優(yōu)化數(shù)據(jù)結(jié)構(gòu)。Dijkstra算法中使用鄰接矩陣存儲(chǔ)具有N個(gè)頂點(diǎn)的圖的

(2)縮小最短路徑節(jié)點(diǎn)選取的搜索范圍。在Dijkstra算法中，圖中除了源點(diǎn)外

的每個(gè)頂點(diǎn)都要經(jīng)歷從未標(biāo)記頂點(diǎn)到標(biāo)記頂點(diǎn)的轉(zhuǎn)變。這種轉(zhuǎn)變過(guò)程需要不斷的掃描大量未標(biāo)記節(jié)點(diǎn)，從中選取一個(gè)最短路徑節(jié)點(diǎn)作為中間節(jié)點(diǎn)。在數(shù)據(jù)量大的情況下，計(jì)算和比較的次數(shù)會(huì)增多，必然會(huì)影響算法的整體計(jì)算速度，降低算法的執(zhí)行效率。可以采用只對(duì)與最短路徑上頂點(diǎn)相鄰的頂點(diǎn)作處理，而對(duì)于其它相離頂點(diǎn)不作處理的方法來(lái)縮小最短路徑節(jié)點(diǎn)的查找范圍，這樣就可以大大提高算法的執(zhí)行效率。

四、Dijkstra算法優(yōu)化思路和步驟

(一)Dijkstra算法優(yōu)化思路

(二)Dijkstra優(yōu)化算法步驟

五、Dijkstra算法和優(yōu)化算法應(yīng)用舉例

圖5-1為有向非負(fù)帶權(quán)圖，求源點(diǎn)0到其余頂點(diǎn)的最短路徑及其最短路徑長(zhǎng)度。

(一)Dijkstra算法求解過(guò)程為

9.將頂點(diǎn)4加入到集合S中，此時(shí)集合S={0，1，2，3，4}=V，算法結(jié)束。

(二)Dijkstra優(yōu)化算法求解過(guò)程為

(三)Dijkstra優(yōu)化算法與Dijkstra算法的比較

1.運(yùn)算次數(shù)的比較

從對(duì)帶權(quán)圖5-1使用Dijkstra算法和Dijkstra優(yōu)化算法求解的過(guò)程中可以看出，Dijkstra的優(yōu)化算法在具體的第二步、第四步中較Dijkstra算法減少了計(jì)算次數(shù)，從整體上減少了比較和計(jì)算的次數(shù)，提高了搜索速度。尤其當(dāng)圖的節(jié)點(diǎn)數(shù)n較大且其鄰接矩陣為稀疏矩陣時(shí)，相對(duì)于Dijkstra算法，優(yōu)化算法在空間復(fù)雜性和時(shí)間復(fù)雜性上都得到了有效的降低。

2.空間復(fù)雜度與時(shí)間復(fù)雜度比較

空間復(fù)雜度比較。Dijkstra算法采用圖的鄰接矩陣存儲(chǔ)圖中頂點(diǎn)與頂點(diǎn)之間的關(guān)系數(shù)據(jù)，需要的存儲(chǔ)空間為，(N為頂點(diǎn)的個(gè)數(shù))。算法的空間復(fù)雜度為。Dijkstra優(yōu)化算法采用鄰接表來(lái)存儲(chǔ)圖的拓?fù)浣Y(jié)構(gòu)，其存儲(chǔ)量為O(M)(M為頂點(diǎn)集合中同頂點(diǎn)關(guān)聯(lián)的所有邊的數(shù)目)，算法的空間復(fù)雜度為O(M)。

時(shí)間復(fù)雜度比較。Dijkstra優(yōu)化算法在搜索最短路徑值的頂點(diǎn)及更新最短路徑值時(shí)，只涉及已標(biāo)記頂點(diǎn)的鄰接點(diǎn)集合和該鄰接點(diǎn)集合與已標(biāo)識(shí)集合的差集兩個(gè)集合中的元素進(jìn)行，算法的執(zhí)行時(shí)間由已標(biāo)識(shí)頂點(diǎn)的鄰接點(diǎn)集合中元素?cái)?shù)量多小而決定，一般情況下，鄰接集合中元素的個(gè)數(shù)往往小于未標(biāo)識(shí)集合中元素的個(gè)數(shù)。由圖中頂點(diǎn)和邊的個(gè)數(shù)，頂點(diǎn)的平均出度為邊的個(gè)數(shù)，n為頂點(diǎn)個(gè)數(shù)。步驟2和3都是搜索與頂點(diǎn)i(i=0,1,2…,n)相鄰頂點(diǎn)的操作，時(shí)間復(fù)雜度為，所以，整個(gè)算法理論上的時(shí)間復(fù)雜度為

結(jié)束語(yǔ)

本文通過(guò)對(duì)Dijkstra算法的分析，發(fā)現(xiàn)了Dijkstra算法在實(shí)際應(yīng)用中存在的不足，導(dǎo)致該算法占用存儲(chǔ)空間大、運(yùn)行時(shí)間長(zhǎng)、效率低，最后針對(duì)算法中存在的不足提出了算法優(yōu)化的方法， 通過(guò)改變存儲(chǔ)圖數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)和縮小搜索標(biāo)識(shí)點(diǎn)范圍的方法，既節(jié)省了計(jì)算機(jī)的存儲(chǔ)空間又提高了算法執(zhí)行的效率，又可以適應(yīng)任何情況的網(wǎng)絡(luò)圖 ，算法性能比較穩(wěn)定。

[1]王曉東.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2011(9).

[2]王秋芬.呂聰穎.周春光.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2011(8).

[3]張永龍.Dijkstra最短路徑優(yōu)化算法[J].南昌工程學(xué)院學(xué)報(bào),2006(3).

[4]王占紅.孫明明.Dijkstra算法的分析與改進(jìn)[J].湖北第二師范學(xué)院學(xué)報(bào),2008(8).

Algorithm analysis and optimization of the shortest path problem based on Dijkstra

Liu Zhao-xia
(Mathematics Department of Jining Teachers College, Jining Inner Mongolia,012000, China)

The Dijkstra algorithm is the most representative of the shortest path algorithm, provides the theoretical basis for solving the shortest path problem in many engineering fields. This paper analyzes the deficiency of the Dijkstra algorithm and this algorithm, and presents a method of optimization of the algorithm, compared with the original algorithm, the results show that algorithm has been improved at run time and efficiency, the storage space are reduced.

graph theory; Dijkstra algorithm; shortest path

O1-0

A

1000-9795（2014）04-0160-02

［責(zé)任編輯：劉麗杰］

2014-02-13

劉朝霞（1980-），女，內(nèi)蒙古烏蘭察布市人，講師，從事高等數(shù)學(xué)教育方向的研究。