基于方向優(yōu)先和對向搜索的改進Dijkstra算法

唐彩紅

(山東萬杰醫(yī)學(xué)院，山東 淄博 255213)

0 引言

近年來，隨著城市規(guī)模的飛速發(fā)展和人們生活質(zhì)量不斷提高，交通線路越來越多而復(fù)雜，汽車銷售量也逐年增加。人們駕車出行時，首要解決的問題是——選擇最短的、合適的道路。因此，最短路徑問題成為交通網(wǎng)絡(luò)研究中的一個重要問題。Dijkstra算法是目前最經(jīng)典、研究最多的一種算法。針對傳統(tǒng)Dijkstra算法的不足，許多學(xué)者進行了一些研究和改進，如:陸檁等提出了限定區(qū)域的搜索方法，姜惠娟則根據(jù)頂點的出度和入度對算法進行了優(yōu)化;還有一些學(xué)者在存儲結(jié)構(gòu)上做了一些改進:如采用鄰接表等，然而，采用這些改進的Dijkstra算法來搜索龐大復(fù)雜的交通網(wǎng)絡(luò)時，占用存儲空間大，搜索效率仍然不高[1-8]。為此，本文通過改進存儲結(jié)構(gòu)，提出一種基于方向優(yōu)先和對向搜索的改進Dijkstra算法，以減少存儲空間，提高搜索效率。

1 傳統(tǒng)Dijkstra算法的弊端

1.1 從搜索方法來分析

傳統(tǒng)Dijkstra算法的基本思想是:按照路徑長度依次遞增的次序生成最短路徑。該算法在搜索最短路徑時需要逐一遍歷網(wǎng)絡(luò)圖中所有頂點，搜索方向具有盲目性，搜索范圍很大，從而導(dǎo)致搜索效率很低[9]。求解搜索效率的公式如下:

由公式(1)可知，其最短路徑搜索效率與需要搜索的頂點數(shù)n成反比。顯然，隨著交通線路和交叉口的增多，采用傳統(tǒng)Dijkstra算法搜索最短路徑時，搜索效率會大大地降低。根據(jù)交通網(wǎng)絡(luò)的空間特性可知[10-12]，從源點到終點的最短路徑方向應(yīng)與源點和終點直接相連的線路方向大致一致，顯然，與源點關(guān)聯(lián)的道路的方向與這條線路的方向偏差越小，即方向間的夾角越小，該道路被選中的概率就會越大。因此，本文根據(jù)這一原理，提出按方向優(yōu)先的搜索方法。在搜索過程中，只需從源點的鄰接頂點中找出與源點的連線方向和源點與終點的連線方向之間夾角最小的頂點，從而能夠避免遍歷網(wǎng)絡(luò)圖中與最短路徑無關(guān)的大量頂點，縮小搜索范圍，減少計算量，提高搜索效率。

然而，對于龐大復(fù)雜的交通網(wǎng)絡(luò)，采用按方向優(yōu)先的單向搜索方法，搜索效率仍然不高。為此，本文提出方向優(yōu)先+對向搜索相結(jié)合的搜索方法。對向搜索是一種能夠縮小搜索范圍的方法[13]。算法中需設(shè)置2個進程，分別從源點和終點同時進行對向搜索，并在搜索過程中都采用按方向優(yōu)先的搜索方法，從而能夠進一步縮小搜索范圍(理想情況下搜索范圍為原來1/2)，加快搜索速度。綜上所述，本文提出了方向優(yōu)先與對向搜索相結(jié)合的搜索方法，以提高搜索效率。

1.2 從存儲空間來分析

傳統(tǒng)Dijkstra算法采用鄰接矩陣來存儲圖的信息。通常情況下，交通網(wǎng)絡(luò)圖對應(yīng)的鄰接矩陣是一個稀疏矩陣，存儲了大量的權(quán)值為0或∞的無效元素，從而浪費了大量的存儲空間，并降低了搜索效率[14]。為此，結(jié)合本文提出的搜索方法，采用頂點-弧聯(lián)合結(jié)構(gòu)來存儲圖中的信息，其中，弧的信息采用鄰接矩陣與判斷矩陣聯(lián)合來存儲，頂點信息采用一維數(shù)組存儲，不僅避免了存儲大量無效元素，而且在節(jié)省存儲空間的同時，還提高了算法的搜索效率。

因此，針對傳統(tǒng)Dijkstra算法的不足，提出了一種改進的Dijkstra算法。通過改進存儲結(jié)構(gòu)和搜索方法，以加快搜索速度，提高搜索效率。

2 改進的Dijkstra算法描述

2.1 存儲結(jié)構(gòu)的定義

首先對交通網(wǎng)絡(luò)地圖進行掃描，然后使用Arc-GIS 9.3 Desktop地理信息系統(tǒng)軟件對掃描圖進行編輯、處理，提取地圖中的路段和路段交叉處，分別將其抽象為圖中的弧和頂點，并保留它們之間的拓?fù)潢P(guān)系，從而生成一個對應(yīng)于交通網(wǎng)路的帶權(quán)圖G。設(shè)圖G含有n個頂點、m條弧。結(jié)合本文提出的搜索方法，本文采用頂點-弧聯(lián)合結(jié)構(gòu)來存儲圖中的信息。

1)頂點的存儲結(jié)構(gòu)。

根據(jù)方向優(yōu)先的搜索方法，本文對頂點結(jié)構(gòu)采用一維數(shù)組vex[N]來存儲，各頂點信息按頂點編號順序存儲，且每個數(shù)組元素包括4項。在遍歷圖中頂點的鄰接點時，循環(huán)次數(shù)可由該頂點的關(guān)聯(lián)弧數(shù)h來確定，從而減少無用的循環(huán)，大大提高了算法的搜索速度。頂點的存儲形式見表1。

表1 頂點的存儲形式

2)弧的存儲結(jié)構(gòu)。

圖中弧的信息采用鄰接矩陣與判斷矩陣聯(lián)合來存儲。

①構(gòu)造圖的鄰接矩陣A。

鄰接矩陣A的行數(shù)為圖G的頂點數(shù)，并按頂點編號由小到大排列;列數(shù)為網(wǎng)絡(luò)圖中頂點的最大關(guān)聯(lián)弧數(shù)(通常交通網(wǎng)中與路口關(guān)聯(lián)的道路不超過4條)。矩陣A中第i行元素的值為與第i個頂點鄰接的頂點編號值，并按由小到大排列，如果該頂點的鄰接頂點數(shù)小于最大關(guān)聯(lián)弧數(shù)4，則該行剩下的元素值全置為0。鄰接矩陣A占用的存儲空間為n×4。

②構(gòu)造圖的關(guān)聯(lián)矩陣B。

關(guān)聯(lián)矩陣B與鄰接矩陣A是對應(yīng)的，其大小與矩陣A相同。將鄰接矩陣A各元素的鄰接頂點的編號值用與其關(guān)聯(lián)的弧上的權(quán)值代替，便得到了鄰接矩陣B。鄰接矩陣B占用的存儲空間也為n×4。

傳統(tǒng)Dijkstra算法的空間復(fù)雜度為O(n2)。顯然，采用本文改進的存儲結(jié)構(gòu)，算法的空間復(fù)雜度為O(n)，節(jié)省了大量存儲空間，提高了搜索速度。

2.2 方向優(yōu)先+對向搜索的搜索描述

傳統(tǒng)Dijkstra算法在搜索最短路徑時需要逐一遍歷網(wǎng)絡(luò)圖中所有頂點，搜索范圍大，搜索效率低。因此，對傳統(tǒng)算法的搜索方法進行改進，提出了方向優(yōu)先+對向搜索的搜索方法。通過采用方向優(yōu)先的搜索方法，縮小搜索范圍，以避免遍歷許多與最短路徑無關(guān)的頂點，從而提高搜索速度;通過采用對向搜索的搜索方法，能夠進一步縮小搜索范圍，加快搜索速度。鑒于此，本算法需設(shè)置2個進程，分別記作P1、P2，并用集合 U1、U2分別來存放 2個進程搜索到的最短路徑上頂點，這些頂點的編號按搜索的順序分別存放在一個一維數(shù)組中?；?.1節(jié)中定義的圖的存儲結(jié)構(gòu)，方向優(yōu)先+對向搜索的搜索算法描述如下:

1)2個進程P1和P2分別同時從源點V0和終點V6出發(fā)(如圖1所示)，進行對向搜索。

圖1 某地區(qū)部分交通網(wǎng)絡(luò)圖

現(xiàn)以從源點出發(fā)進行搜索的進程P1為例，從鄰接矩陣A中依次查找該源點的還未加入到最短路徑集合U1中的鄰接頂點，并計算該頂點與源點連線方向的斜率、源點與終點連線方向的斜率，進而計算出這2連線方向之間的夾角α。若設(shè)待搜頂點、源點和終點的坐標(biāo)分別為(x，y)、(xc，yc)、(xr，yr)，則夾角α的計算公式為:

其中:

2)按照方向優(yōu)先的原則，2進程分別選取夾角最小的頂點，并將選取的頂點分別加入到集合U1和U2中。

如圖1所示，2進程分別同時從源點V0與終點V6開始對向搜索。進程P1搜索:與源點V0關(guān)聯(lián)的頂點中，V2與V0的連線方向和V0與V6的連線方向之間的夾角最小，應(yīng)選取頂點V2并將該頂點的信息加入到集合U1中;同理，進程P2選取頂點V5并加入到集合 U2中;U1={V0，V2}，U2={V6，V5}，如圖 1 所示，2粗線弧V0V2和V6V5分別為2進程搜索到的最短路徑。

3)現(xiàn)設(shè)Si為P1進程進行第i步搜索時搜索到的頂點在直線V0V6上的投影點和源點V0之間的直線長度，Si'為P2進程進行第i步搜索時搜索到的頂點在直線V0V6上的投影點和終點V6之間的直線長度，S為直線V0V6的長度。則:

同理可求得S'i，然后進行如下判斷:

①若Si+S'i=S或P1進程在第i步搜索到的頂點恰為P2進程在第i－1步搜索到的頂點且P2進程在第i步搜索到的頂點恰為P1進程在第i－1步搜索到的頂點，則2進程停止對向搜索，并轉(zhuǎn)入步驟4)。

②若Si+S'i＜S，則把步驟2)中選取的2頂點分別作為2進程的源點，然后轉(zhuǎn)入步驟1)繼續(xù)搜索。

③若Si+S'i＞S，則說明2進程搜索到最短路徑無法匯合，2進程應(yīng)分別沿著各自的方向繼續(xù)搜索，即反復(fù)執(zhí)行步驟1)和2)，直到2進程搜索到源點或終點，則搜索結(jié)束。最后從集合U1和U2中選取最短路徑長度較小者作為所求最短路徑，并轉(zhuǎn)入步驟5)。

4)將集合U1和U2進行合并，即可得到源點到終點最短路徑。

5)搜索算法結(jié)束。

按照上面描述的搜索算法，即可求得圖2中粗線所示的從源點V0到終點V6最短路徑，即V0→V2→V5→V6。

圖2 方向優(yōu)先和對向搜索圖

2.3 性能分析

傳統(tǒng)Dijkstra算法的空間復(fù)雜度為O(n2)。若采用本文改進的存儲結(jié)構(gòu)，算法的空間復(fù)雜度減少到O(n)。圖的存儲結(jié)構(gòu)若采用鄰接矩陣，搜索各個頂點的鄰接頂點時所需時間均為O(n)，而采用本文改進的存儲結(jié)構(gòu)，搜索時間則減少到O(h)(h為該頂點關(guān)聯(lián)的弧數(shù)，h≤4)?；诒疚母倪M的存儲結(jié)構(gòu)，采用方向優(yōu)先的搜索方法，避免了遍歷圖中與最短路徑上無關(guān)的大量頂點，算法的時間復(fù)雜度大大降低了。若采用方向優(yōu)先+對向搜索相結(jié)合的搜索方法，使算法具有并行化策略，可使算法的時間復(fù)雜度在原有基礎(chǔ)上進一步降低;當(dāng)搜索含有較少的頂點和弧的交通網(wǎng)時，采用對向搜索的搜索方法，搜索效率的提高并不明顯;但搜索較復(fù)雜的交通網(wǎng)時，搜索效率就會明顯地提高，最理想情況下可使算法的時間復(fù)雜度減少到原來一半，然而最壞的情況下時間復(fù)雜度與單向搜索的算法相同。

3 應(yīng)用實例

為驗證改進的Dijkstra算法的性能，實驗選取山東省某區(qū)域作為研究對象，并設(shè)定好出發(fā)地和目的地。首先采用ArcGIS 9.3 Desktop軟件對該區(qū)域進行編輯并抽象成帶權(quán)圖，該圖含有75個頂點。分別對改進的Dijkstra算法和傳統(tǒng)Dijkstra算法進行模擬搜索最短路徑實驗，最短路徑搜索完畢后，統(tǒng)計出2種算法所遍歷搜索的總頂點數(shù)，并由此求出2種算法的搜索效率。實驗結(jié)果如表2所示。

表2 2種算法性能比較表

由表2可看出，若采用傳統(tǒng)Dijkstra算法，需搜索的頂點總數(shù)為74，計算量大且存儲空間大，搜索效率為84.3%;若采用本文提出的改進的Dijkstra算法，存儲空間大大減少了，需搜索的頂點數(shù)減少到17，搜索效率由84.3%提高到97.2%。由此可見:采用改進的Dijkstra算法，在減少存儲空間的同時，加快了搜索速度，提高了搜索效率，表明改進的Dijkstra算法是有效的。

4 結(jié)束語

本文針對傳統(tǒng)Dijkstra算法的不足，提出了一種基于方向優(yōu)先和對向搜索的改進Dijkstra算法。通過改進存儲結(jié)構(gòu)和搜索方法，節(jié)省了大量存儲空間，提高了搜索速度。然而，本文提出的改進的Dijkstra算法求解交通網(wǎng)絡(luò)中的最短路徑時，并沒有考慮道路的擁塞情況、障礙物存在的情況等，因此還有待于進一步改進，以更好地滿足人們的需求。

[1] 陸檁，李世杰，王貴甫，等.港區(qū)導(dǎo)航系統(tǒng)中最短路徑搜索算法[J].計算機工程，2011，37(17):279-281.

[2] 姜惠娟.Dijkstra最短路徑算法的優(yōu)化及在應(yīng)急交通中的應(yīng)用[J].泰山學(xué)院學(xué)報，2013，35(6):65-68.

[3] 李桂玲.Dijkstra算法的一種改進[J].電腦開發(fā)與應(yīng)用，2009，22(7):13-14.

[4] 徐鳳生.最短路徑的求解算法[J].計算機應(yīng)用，2004，24(5):88-89.

[5] 周培德.交通道路網(wǎng)中任意兩點之間最短路徑的快速算法[J].計算機工程與科學(xué)，2002，24(4):35-37.

[6] 肖?？?最短路徑算法在交通導(dǎo)航方面的應(yīng)用和改進[J].計算機應(yīng)用與軟件，2011，28(9):298-300.

[7] 田昇.基于Dijkstra算法的物流配送系統(tǒng)最短路徑程序設(shè)計[J].交通標(biāo)準(zhǔn)化，2009(13):89-92.

[8] 黃睿.Dijkstra算法在物流中的優(yōu)化與實現(xiàn)[J].計算機時代，2012(2):10-12.

[9] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學(xué)出版社，2002.

[10] 王凌，段江濤，王保保.GIS中最短路徑的算法研究與仿真[J].計算機仿真，2005，22(1):117-120.

[11] 李健.基于Dijkstra最短路徑算法的優(yōu)化研究[J].渭南師范學(xué)院學(xué)報，2009，24(5):61-64.

[12] 王華.基于Dijkstra算法的物流配送最短路徑算法研究[J].計算機與數(shù)字工程，2011，39(3):48-50.

[13] 郭晶，劉廣軍，董緒榮，等.嵌入式導(dǎo)航系統(tǒng)的最短路徑算法研究[J].裝備指揮技術(shù)學(xué)院學(xué)報，2005，16(5):100-103.

[14] 章炯民，竇亮，黃國興.數(shù)據(jù)結(jié)構(gòu)與算法教程[M].上海:華東師范大學(xué)出版社，2007.

[15] 劉迎春.一種實用的最短路徑求解算法[J].浙江工業(yè)大學(xué)學(xué)報，2000，28(2):169-173.

[16] 王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實現(xiàn)[J].微計算機信息，2007，23(33):275-277.

[17] 徐濤，鄭英，周念.物流最短路徑規(guī)劃最優(yōu)化計算方法研究[J].物流技術(shù)，2013，32(7):236-238.