馮瑩瑩

(阜陽師范學(xué)院信息工程學(xué)院,安徽 阜陽 236041)

基于GIS的Dijstra最短路徑算法研究

馮瑩瑩

(阜陽師范學(xué)院信息工程學(xué)院,安徽 阜陽 236041)

最短路徑是GIS在應(yīng)用中的主要問題之一，目前提出的求取最短路徑的算法很多，其中Dijkstra算法是使用最為普遍。通過對傳統(tǒng)的Dijkstra算法在GIS應(yīng)用中的分析和研究,對算法的數(shù)據(jù)結(jié)構(gòu)和存儲方式進行了優(yōu)化。復(fù)雜性分析比較以及仿真分析證明該改進算法的效率優(yōu)于傳統(tǒng)Dijkstra算法，既節(jié)省了存儲空間，又提高了程序執(zhí)行效率。

GIS；數(shù)據(jù)結(jié)構(gòu)；Dijkstra算法；存儲方式

1 傳統(tǒng)Dijkstra算法

Dijkstra 算法是以路徑長度遞增的次序來產(chǎn)生最短路徑的算法，主要通過一個源節(jié)點不斷增長找到最短路徑。下面根據(jù)最短路徑算法即鄰接矩陣結(jié)構(gòu)形式的Dijkstra算法來介紹其實現(xiàn)過程。

設(shè)一幅具有N個節(jié)點的帶權(quán)有向圖G,用鄰接矩陣Cost來表示，其中弧〈Vi,Vj〉的權(quán)值以Cost[i,j]來表示，當(dāng)Vi到Vj走不通時,則總鄰接矩陣表示為Cost[i,j]=∞。設(shè)S為起始點，同時設(shè)置一個輔助向量DI，每個DI[i]表示從起始點S到每個終點Vi的最小權(quán)值。根據(jù)設(shè)置的鄰接矩陣特點，設(shè)所有結(jié)點的集合稱為U，并令P為已經(jīng)找到的從起點出發(fā)的最短路徑的終點集合,那么其向量的初始值為：DI[i]=Cost[P,i]，Vi∈U。其中P={VP},根據(jù)最短路徑算法公式計算分析，從VP出發(fā)到圖G上其他所有結(jié)點Vi可能達到的最短路徑長度為設(shè)定的初始值公式值。

步1 令P=P∪{Vj}，要想計算得到從VP出發(fā)的最短路徑的終點節(jié)點，選擇Vj,使得DI[j]=min{DI[i]|Vi∈U-P}，這個Vj就是獲得的最終節(jié)點。

步2U-P作為集合，其中包含了很多頂點，為了獲取路徑長度，可以修改從VP到頂點VK的最短路徑長度。當(dāng)DI[k]> Cost[j,k]+DI[j],轉(zhuǎn)步3。

步3 當(dāng)出現(xiàn)DI[k]> Cost[j,k] + DI[j]時，就將DI[k]=DI[j]+Cost[j,k]直接賦值操作并重復(fù)操作步2和步3共N-1次,該路徑是各權(quán)值遞增的序列。

上面的三步法求得最短路徑算法采用的是的鄰接矩陣Cost來存儲網(wǎng)絡(luò)圖，存儲的空間范圍是N×N,當(dāng)圖形相對大時，存儲的大部分矩陣都是沒有意義的[1]。在遍歷過程中，Dijkstra算法主要還是按標(biāo)記法來實現(xiàn)最短路徑的搜索，即從未標(biāo)記的點中找到權(quán)值最小的節(jié)點，但會出現(xiàn)一種現(xiàn)象，當(dāng)這些未標(biāo)記節(jié)點以無序的形式存儲在一個鏈表或數(shù)組中，如果想獲取最小權(quán)值節(jié)點就必須將這鏈表或者數(shù)組中的所有未標(biāo)記的節(jié)點進行掃描，如果是這樣，當(dāng)一個圖集中有大量數(shù)據(jù)的情況下，就會給最短路徑算法的計算速度帶來限制。當(dāng)一個系統(tǒng)被N多用戶并發(fā)訪問時就會出現(xiàn)服務(wù)器癱瘓，正是考慮到這種多發(fā)訪問出現(xiàn)的問題，最短路徑采用了同樣的原理，算法實現(xiàn)原理中的關(guān)鍵技術(shù)為松弛技術(shù)，通過反復(fù)減小每個頂點實際路徑權(quán)限的范圍值，通過迭代找到最短路徑值。

2 Dijkstra算法優(yōu)化

在GIS系統(tǒng)中要求解2點之間的最優(yōu)路徑，即最短路徑算法的實現(xiàn)，具有速度快、占用資源少、穩(wěn)定性強等優(yōu)點的Dijkstra 算法是解決該類問題的有效算法，但在特定的環(huán)境和大量數(shù)據(jù)情況下，Dijkstra算法也出現(xiàn)了瓶頸：其遍歷的未標(biāo)記節(jié)點過多，重復(fù)迭代，導(dǎo)致速度相對下降。為此，筆者對Dijkstra算法進行了深入的分析和研究，采用一種堆排序和鄰接表的面向?qū)ο蟮腄ijkstra算法的改進算法，具體的算法是基于傳統(tǒng)Dijkstra算法本體，對其數(shù)據(jù)結(jié)構(gòu)和存儲方式進行了優(yōu)化，從而優(yōu)化了Dijkstra 算法。

2.1 存儲方式改進

在GIS中存在著很多重要的空間數(shù)據(jù)，如線路、標(biāo)志物、道路燈等，這些都要進行最短路徑的計算，而Dijkstra算法是圖論計算最短路徑的有效算法，因此，GIS中的所有空間數(shù)據(jù)都要將其轉(zhuǎn)化為結(jié)點和邊的關(guān)系，從而形成圖的結(jié)構(gòu)和網(wǎng)絡(luò)拓樸圖的效果。在網(wǎng)絡(luò)圖中的線和點是算法的單位元，Dijkstra算法主要通過這些結(jié)點進行計算，GIS中的點、線、面等空間幾何數(shù)據(jù)與面沒有計算關(guān)系，但GIS中的地理位置信息具有方向性，這些結(jié)點、邊、方向以及結(jié)點的鏈接點都是計算最短路徑的重要信息，在計算過程中都賦有權(quán)值[2]。下面主要從3個方面進行優(yōu)化改進。

表1 算法節(jié)點聲明

(1)根據(jù)GIS圖中的形成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖的相關(guān)重要參數(shù)進行設(shè)置和計算。算法的存儲方式以面向?qū)ο鬄闃?biāo)準(zhǔn)進行設(shè)定，設(shè)S為帶權(quán)有向圖，L為邊，V為結(jié)點，其中圖中的結(jié)點數(shù)為n，邊數(shù)為m，將圖中的任一結(jié)點設(shè)為j，而這個j結(jié)點的直接前趨結(jié)點設(shè)為k，P為起始點，U為終點。算法優(yōu)化的存儲方式是面向?qū)ο蟮模虼瞬捎肑ava語言進行名詞聲明和定義，其中對結(jié)點和相關(guān)弧信息進行封裝，具體如表1所示。

2)在算法實現(xiàn)過程中存在很多對象類，其中的Lxctor類就封裝了集合U-P的結(jié)點列表，并且按照結(jié)點順序進行存放。Dijkstra算法中包含一組對象的對象類，其中Lxctor被定義為收集類對象，允許動態(tài)的創(chuàng)建數(shù)組，也允許對鏈表中的結(jié)點進行增加和刪除操作，在Java技術(shù)平臺下支持的收集類包括LinkedList、Vector、Hashtable等。

3)在Java技術(shù)平臺下，算法中的最短路徑列表即從起點到終點的最短路徑，設(shè)為對象類critHash，critHash和Lxctor一樣也是一個收集類對象，也是Hashtable數(shù)組中的一個對象類。當(dāng)然在Java語言中這2大類也是有所區(qū)別的，圖信息中的每一個對象元素都對應(yīng)一個關(guān)鍵字，即關(guān)鍵字與對象元素是一一對應(yīng)的關(guān)系，而算法中的對象類critHash具有這樣的特征[3]。通過該對象類將每一個結(jié)點到其他結(jié)點的最短路徑進行封裝，并賦予一個關(guān)鍵字，每當(dāng)搜索過程中發(fā)現(xiàn)已經(jīng)做過標(biāo)記關(guān)鍵字則該條路徑搜索結(jié)束，通過這樣的對象類封裝，可得到結(jié)點的最短路徑列表，減少搜索范圍。

圖1 數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度優(yōu)化流程

在存儲方式優(yōu)化過程中還用到了3大輔助對象類：cVeetor、cHash和sHash，對象類cVeetor封裝與源點相鄰但還未被訪問過的結(jié)點列表，對象類sHash用于封裝出度大于零的結(jié)點，對象類cHash則是與sHash中每個結(jié)點元素對應(yīng)的相鄰結(jié)點列表。通過采用這些對象類對圖中的信息進行關(guān)聯(lián)和權(quán)值計算，最后優(yōu)化了最短路徑算法。

2.2 數(shù)據(jù)結(jié)構(gòu)優(yōu)化

在算法數(shù)據(jù)結(jié)構(gòu)中，對點和弧都進行了編號和定義，1個弧段是由若干位進行表示，包括弧段編號及權(quán)值、弧段起始節(jié)點編號、弧段結(jié)束節(jié)點編號， GIS圖中的所有點在數(shù)據(jù)結(jié)構(gòu)中被標(biāo)識為一些節(jié)點，并形成對應(yīng)數(shù)據(jù)信息。正是因為這些點是連接弧段的起始和結(jié)束點，在數(shù)據(jù)結(jié)構(gòu)的所有圖信息中，根據(jù)點和邊的關(guān)聯(lián)，算法中可實現(xiàn)各種矩陣，方便實現(xiàn)各種搜索和運算。因此采用優(yōu)質(zhì)穩(wěn)定的數(shù)據(jù)結(jié)構(gòu)可大大縮短Dijkstra算法的計算時間，利用先進數(shù)據(jù)結(jié)構(gòu)體系完成算法從時間復(fù)雜度由二階降到對數(shù)階的完美過渡[4]。具體實現(xiàn)如圖1所示。

3 復(fù)雜性分析比較與仿真

3.1 復(fù)雜性分析及比較

1)時間復(fù)雜度分析 筆者采用的是堆棧式的鄰接表方式對存儲方式和數(shù)據(jù)結(jié)構(gòu)進行優(yōu)化。首先將圖中的信息節(jié)點和弧進行聲明定義，并構(gòu)建弧點矩陣結(jié)構(gòu)，通過動態(tài)的收集類進行動態(tài)的遍歷數(shù)組，對最短路徑權(quán)值進行存儲，每一次的遍歷都會得到一個節(jié)點列表，并對這些節(jié)點信息值進行排序，完成優(yōu)先遍歷表，這樣大大提高了搜索的時間，通過采用基數(shù)堆與Fibonacci堆的組合,其時間復(fù)雜度為O(m+nlogn)，在一定程度上提高了運算速度。與傳統(tǒng)的Dijkstra算法相比較，具有很大的時間效率優(yōu)勢。

表2 搜索節(jié)點數(shù)量對比

2)空間復(fù)雜度分析 筆者通過改變存儲方式，將一個GIS圖分為節(jié)點和弧段，實現(xiàn)節(jié)點弧關(guān)聯(lián)結(jié)構(gòu)體，改變了節(jié)點的存儲量，減少了遍歷的節(jié)點數(shù)，存儲量為O(L+2N)(L為節(jié)點列表中同節(jié)點關(guān)聯(lián)的所有弧段數(shù)目)。同時設(shè)兩個數(shù)組來存儲求得的起點到其他所有節(jié)點的最短路徑值以及排序節(jié)點，緩沖搜索時間。而傳統(tǒng)Dijkstra算法的空間復(fù)雜度為O(N)，相比較而言，提供了存儲效率，節(jié)省了空間[5]。

3.2 數(shù)據(jù)仿真實現(xiàn)

針對GIS圖的最短路徑算法的數(shù)據(jù)仿真，采用了硬件設(shè)備為主頻700MHz,內(nèi)存為1G，安裝系統(tǒng)為WindowsXP,并通過.NET Frameworks 3.5[6]實現(xiàn)了算法。搜索節(jié)點數(shù)量對比結(jié)果如表2所示。由表2可知，對Dijkstra算法的存儲方式和數(shù)據(jù)結(jié)構(gòu)的優(yōu)化可以提高算法的效率和穩(wěn)定性。

4 結(jié) 語

提出了一種基于堆排序和鄰接表的面向?qū)ο蟮腄ijkstra算法的改進算法，結(jié)合傳統(tǒng)Dijkstra算法的現(xiàn)狀，分析了其在求解最短路徑上的瓶頸，對算法實現(xiàn)過程中數(shù)據(jù)存儲方式和數(shù)據(jù)結(jié)構(gòu)進行了優(yōu)化[7]，通過對改進后的算法和之前算法空間和時間復(fù)雜度上的分析和比較以及仿真試驗證明，優(yōu)化后的算法具有一定的高效性和穩(wěn)定性。

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

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

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

[4]陳述彭,魯愛軍,周成虎.地理信息系統(tǒng)導(dǎo)論[M]. 北京:科學(xué)出版社,2000.

[5]盧開澄,盧華明.圖論及其應(yīng)用[M]. 第2版.北京:清華大學(xué)出版社,1997.

[6]嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,1997.

[7]陸鋒.最短路徑算法:分類體系與研究進展[J]. 測繪學(xué)報,2001(15)：116-118.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.10.034

TP311.12;O241

A

1673-1409(2012)10-N110-03