馮瑩瑩

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

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

馮瑩瑩

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

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

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

1 傳統(tǒng)Dijkstra算法

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

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

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

步2U-P作為集合，其中包含了很多頂點(diǎn)，為了獲取路徑長度，可以修改從VP到頂點(diǎn)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]時(shí)，就將DI[k]=DI[j]+Cost[j,k]直接賦值操作并重復(fù)操作步2和步3共N-1次,該路徑是各權(quán)值遞增的序列。

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

2 Dijkstra算法優(yōu)化

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

2.1 存儲(chǔ)方式改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

表2 搜索節(jié)點(diǎn)數(shù)量對(duì)比

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

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

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

4 結(jié) 語

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

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

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

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

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

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

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

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

[編輯] 洪云飛

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

TP311.12;O241

A

1673-1409(2012)10-N110-03