一種電子地圖最短路徑算法研究

王　昊

[摘要]針對(duì)最短路徑算法在電子地圖領(lǐng)域的運(yùn)用，分析、實(shí)現(xiàn)并驗(yàn)證Dijkstra算法在該領(lǐng)域運(yùn)用的可行性。還指出Dijkstra算法的不足，以及解決思路。

[關(guān)鍵詞]電子地圖 最短路徑 算法

中圖分類(lèi)號(hào)：TP3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597（2009）0310066－02

一、引言

所謂最優(yōu)路徑是指網(wǎng)絡(luò)兩個(gè)結(jié)點(diǎn)之間阻抗最小的路徑。最短路徑分析是地理信息系統(tǒng)網(wǎng)絡(luò)分析中的基本功能，在很多領(lǐng)域應(yīng)用十分廣泛。最短路徑分析以路徑網(wǎng)絡(luò)為基礎(chǔ)，用戶(hù)通過(guò)給出起點(diǎn)和終點(diǎn)，并賦予一定的權(quán)值，可得到從起點(diǎn)到終點(diǎn)的最短路線(xiàn)圖。通常的最短路徑算法往往是建立在抽象的數(shù)學(xué)模型之上。在網(wǎng)絡(luò)模型上，實(shí)際的路徑被抽象為網(wǎng)絡(luò)中的一條邊，實(shí)際路徑的長(zhǎng)度與網(wǎng)絡(luò)邊的長(zhǎng)度可以不成比例，以邊的權(quán)值來(lái)表征路徑的長(zhǎng)度，在該網(wǎng)絡(luò)上求某點(diǎn)到其它任一點(diǎn)的最短路徑的方法，被稱(chēng)為最短路徑算法。Dijkstra算法是目前多數(shù)系統(tǒng)解決最短路徑問(wèn)題采用的理論基礎(chǔ)。不僅可以找到最短的路徑，而且可以給出從起點(diǎn)出發(fā)到圖中所有節(jié)點(diǎn)的最短路徑，這正是此種算法的特色。

二、Dijkstra算法

（一）算法的基本思想

基本思想：設(shè)置一個(gè)頂點(diǎn)的集合s，并不斷地?cái)U(kuò)充這個(gè)集合，一個(gè)頂點(diǎn)屬于集合s當(dāng)且僅當(dāng)從源點(diǎn)到該點(diǎn)的路徑已求出。開(kāi)始時(shí)s中僅有源點(diǎn)，并且調(diào)整非s中點(diǎn)的最短路徑長(zhǎng)度，找當(dāng)前最短路徑點(diǎn)，將其加入到集合s，直到終點(diǎn)在s中。

（二）算法原理

Dijkstra算法將網(wǎng)絡(luò)節(jié)點(diǎn)分為未標(biāo)示節(jié)點(diǎn)、臨時(shí)標(biāo)示節(jié)點(diǎn)和已標(biāo)示節(jié)點(diǎn)3種類(lèi)型。開(kāi)始網(wǎng)絡(luò)搜索時(shí)，所有節(jié)點(diǎn)首先初始化為未標(biāo)示節(jié)點(diǎn)，在搜索過(guò)程中和最短路徑節(jié)點(diǎn)相連通的節(jié)點(diǎn)記為臨時(shí)標(biāo)示節(jié)點(diǎn)，每一次循環(huán)從臨時(shí)節(jié)點(diǎn)找到的距源點(diǎn)路徑最短的節(jié)點(diǎn)記為已標(biāo)示節(jié)點(diǎn)，直到找到目標(biāo)節(jié)點(diǎn)或者所有節(jié)點(diǎn)都成為已標(biāo)示節(jié)點(diǎn)為止。下面是該算法的描述。

1．用帶權(quán)的鄰接矩陣Cost來(lái)表示帶權(quán)的n個(gè)節(jié)點(diǎn)的有向圖，Cost[i，j]表示弧的權(quán)值，如果從vi到vj不連通，則Cost[i，j]=∞。圖1表示了一個(gè)帶權(quán)有向圖以及其鄰接矩陣。

然后，引進(jìn)一個(gè)輔助向量Dist，每個(gè)分量Dist[i]表示從起始點(diǎn)到每個(gè)終點(diǎn)vi的最短路徑長(zhǎng)度。假定起始點(diǎn)在有向圖中的序號(hào)為i0，并設(shè)定該向量的初始值為：Dist[i]=Cost[i0，i]，vi∈V。令S為已經(jīng)找到的從起點(diǎn)出發(fā)的最短路徑的終點(diǎn)的集合。

2．選擇Vj，使得Dist[j]=Min{Dist[i]|Vi∈V-S}，vi∈V。Vj就是當(dāng)前求得的一條從vi0出發(fā)的最短路徑的終點(diǎn)，令，S=S∪{vj}。

3．修改從vi0出發(fā)到集合V-S中任意一頂點(diǎn)vk的最短路徑長(zhǎng)度。如果Dist[j]+Cost[j，k]

[j,k]。

4．重復(fù)第2、3步操作共n-1次，由此求得從vi0出發(fā)的到圖上各個(gè)頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。

在應(yīng)用中，采用Dijkstra算法計(jì)算兩點(diǎn)之間的最短路徑和求從一點(diǎn)到其它所有點(diǎn)的最短路徑所需要的時(shí)間是一樣的，算法時(shí)間復(fù)雜度為O（n2）。

（三）算法步驟

設(shè)帶權(quán)圖表示為G=，其中，V是圖中頂點(diǎn)的集合，E是邊的集合，W是相應(yīng)的邊的權(quán)的集合。

設(shè)帶權(quán)圖G=是n階簡(jiǎn)單帶權(quán)圖，W(Vi，Vj)大于等于零（即第i條邊的權(quán)大于等于零），若頂點(diǎn)Vi與Vj不相鄰，則令W(Vi，Vj)=∞，求G=中Vo到其余各個(gè)頂點(diǎn)的最短路徑。

設(shè)L是G中的一條路，把路L上帶權(quán)總和稱(chēng)為L(zhǎng)的權(quán)和，記為|L|，又設(shè)P(G)是權(quán)圖中所有頂點(diǎn)的集合，S是其中某些點(diǎn)組成的集合，u0是S中的一個(gè)點(diǎn)，S=P(G)S，把從u0出發(fā)到S中點(diǎn)的具有最小權(quán)和的路徑稱(chēng)為u0到S的距離，記為d(u0,S)，從而求出u0到其余頂點(diǎn)的最短路徑。

（四）算法的瓶頸

在原始Dijkstra算法的過(guò)程中，核心步驟就是從未標(biāo)記的點(diǎn)中選擇一個(gè)權(quán)值最小的弧段，這是一個(gè)循環(huán)比較的過(guò)程，若不采用任何技巧，未標(biāo)記點(diǎn)將以無(wú)序的形式存放在一個(gè)鏈表或數(shù)組中。則要選擇一個(gè)權(quán)值最小的弧段就必須把所有的點(diǎn)都掃描一遍，在大數(shù)據(jù)量的情況下，是一個(gè)制約計(jì)算速度的瓶頸。

三、Dijkstra算法的程序?qū)崿F(xiàn)

（一）基本思路

采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路。設(shè)G為賦權(quán)網(wǎng)絡(luò)有向圖，權(quán)值即為邊的長(zhǎng)度。該算法是求G中從頂點(diǎn)u0到其余各點(diǎn)的最短路。

S：已知最短路徑的頂點(diǎn)集。對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（l(v),z(v)），

其中：l(v)：表示從頂點(diǎn)u0到v的一條路的長(zhǎng)度。z(v)：v的父親點(diǎn)，用以確定最短的路線(xiàn)。

算法的過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終l(v)為從頂點(diǎn)u0到v的最短路的長(zhǎng)度。輸入為長(zhǎng)度值鄰接矩陣ω(U,V)。u：起點(diǎn)標(biāo)號(hào)；v：終點(diǎn)標(biāo)號(hào)。程序中的u和v是兩個(gè)變量，不斷被賦予新值。

算法流程圖如圖2所示。

（二）程序代碼

算法流程分析的是從固定頂點(diǎn)u0到其余各點(diǎn)的最短路，而作者要解決的是從任意頂點(diǎn)m到任意頂點(diǎn)n的最短路，本質(zhì)算法并不改變，只是針對(duì)不同的m選取不同的u0，再?gòu)囊唤M計(jì)算結(jié)果中選取l(n)和z(n)即可。

Dijkstra函數(shù)帶有一個(gè)字符串型的參數(shù)，用來(lái)表示傳遞數(shù)組名matrix_name，二維數(shù)組matrix()經(jīng)過(guò)多次迭代，最終得到m點(diǎn)到其它各點(diǎn)的最短距離，這些距離值構(gòu)成數(shù)組l(i)，所要求m到n的距離即求出l(n)。代碼如下：

Private Function Dijkstra(matrix_name As String)；Dim s(50)As Single；Dim u,v As Single；Dim matrix

()As Double；ReDim matrix(pNum,pNum)；'如果數(shù)組名為path_noright，調(diào)用該數(shù)組'；If matrix_name="path_noright"Then；For i=LBound(path_noright)To UBound(path_noright)；For j=LBound(path_noright)To UBound(path_noright)；matrix(i,j)=path_noright(i,j)；Next j；Next i；'如果數(shù)組名為path_right，調(diào)用該數(shù)組'；ElseIf matrix_name="path_right"Then；For i=LBound(path_right)To UBound(path_right)；For j=LBound(path_right)To UBound(path_right)；matrix(i,j)=path_right(i,j)；Next j；Next i；End If；'獲取m行的值，保存在l()中'；For i=0 To pNum；l(i)=matrix(m,i)；z(i)=m'z()中保存到達(dá)終點(diǎn)的前一個(gè)點(diǎn)；Next i；s(0)=0；u=s(0)；k=0；Do While ks(j)Then；If l(i)>l(u)+matrix(u,i)Then；l(i)=l(u)+matrix(u,i)；z(i)=u；End If；End If；Next j；Next i；Dim ll(50)As Double；For i=0 To pNum；ll(i)=l(i)；Next i；For i=0 To pNum；For j=0 To k；If i<>s(j)Then；ll(i)=ll(i)；Else；ll(i)=1E+38；End If；Next j；Next i；Dim lv As Double；lv=1E+38；For i=0 To pNum；If ll(i)

四、結(jié)束語(yǔ)

本文分析并總結(jié)了Dijkstra算法的思路與編程實(shí)現(xiàn)過(guò)程，驗(yàn)證了其在雖短路徑算法上的優(yōu)勢(shì)和不足之處，證明其在電子地圖上運(yùn)用所具有的優(yōu)勢(shì)，得出Dijkstra算法在電子地圖等領(lǐng)域運(yùn)用的寬廣前景。

參考文獻(xiàn)：

[1]董涌江，GIS網(wǎng)絡(luò)分析功能的實(shí)現(xiàn)[J].三晉測(cè)繪，2003,12(2):89～92.

[2]鄔倫、劉瑜、張晶等，地理信息系統(tǒng)的原理、方法和應(yīng)用[M].科學(xué)出版社，2001,4～20.

[3]趙靜、但琦、嚴(yán)尚安等，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].高等教育出版社，2000,15～24.

[4]鮑培明，距離尋優(yōu)中Dijkstra算法的優(yōu)化[J].計(jì)算機(jī)研究與發(fā)展，2001,3(1):76～79.

[5]張貴軍、吳惕華，GIS線(xiàn)形矢量圖形最優(yōu)路徑算法研究及仿真實(shí)現(xiàn)[J].系統(tǒng)仿真學(xué)報(bào)，2003,4(3):7～9.

作者簡(jiǎn)介：

王昊，男，漢族，北京人，學(xué)歷本科，湖北交通職業(yè)技術(shù)學(xué)院，助理講師，研究方向?yàn)樗惴ㄔO(shè)計(jì)。