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

王　昊

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

[關鍵詞]電子地圖 最短路徑 算法

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597（2009）0310066－02

一、引言

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

二、Dijkstra算法

（一）算法的基本思想

基本思想：設置一個頂點的集合s，并不斷地擴充這個集合，一個頂點屬于集合s當且僅當從源點到該點的路徑已求出。開始時s中僅有源點，并且調整非s中點的最短路徑長度，找當前最短路徑點，將其加入到集合s，直到終點在s中。

（二）算法原理

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

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

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

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

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

[j,k]。

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

在應用中，采用Dijkstra算法計算兩點之間的最短路徑和求從一點到其它所有點的最短路徑所需要的時間是一樣的，算法時間復雜度為O（n2）。

（三）算法步驟

設帶權圖表示為G=，其中，V是圖中頂點的集合，E是邊的集合，W是相應的邊的權的集合。

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

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

（四）算法的瓶頸

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

三、Dijkstra算法的程序實現(xiàn)

（一）基本思路

采用樹生長的過程來求指定頂點到其余頂點的最短路。設G為賦權網(wǎng)絡有向圖，權值即為邊的長度。該算法是求G中從頂點u0到其余各點的最短路。

S：已知最短路徑的頂點集。對每個頂點，定義兩個標記（l(v),z(v)），

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

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

算法流程圖如圖2所示。

（二）程序代碼

算法流程分析的是從固定頂點u0到其余各點的最短路，而作者要解決的是從任意頂點m到任意頂點n的最短路，本質算法并不改變，只是針對不同的m選取不同的u0，再從一組計算結果中選取l(n)和z(n)即可。

Dijkstra函數(shù)帶有一個字符串型的參數(shù)，用來表示傳遞數(shù)組名matrix_name，二維數(shù)組matrix()經(jīng)過多次迭代，最終得到m點到其它各點的最短距離，這些距離值構成數(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，調用該數(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，調用該數(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()中保存到達終點的前一個點；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)

四、結束語

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

參考文獻：

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

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

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

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

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

作者簡介：

王昊，男，漢族，北京人，學歷本科，湖北交通職業(yè)技術學院，助理講師，研究方向為算法設計。