矢量地圖中一種求最短路徑的快速算法

殷雯+馬佩勛

摘 要：在分析總結(jié)了經(jīng)典Dijkstra算法的基礎(chǔ)上，提出了求最短路徑的一種快速實(shí)現(xiàn)算法，根據(jù)算法的復(fù)雜度與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n成線性關(guān)系即O（n）的特點(diǎn)，給出了該算法的具體實(shí)現(xiàn)結(jié)構(gòu)。

關(guān)鍵詞：最短路徑算法;城市道路網(wǎng)絡(luò);地理信息系統(tǒng);經(jīng)典Dijkstra算法

中圖分類號：TP391 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A ? ? ? ? ? ? ? ? 文章編號：2095-1302（2015）09-00-03

0 ?引 ?言

最短路徑問題（SP）是最基本的網(wǎng)絡(luò)優(yōu)化問題之一，在交通網(wǎng)絡(luò)分析系統(tǒng)中占有重要地位，是其它網(wǎng)絡(luò)優(yōu)化算法的基礎(chǔ)。最短路徑問題在實(shí)際中常用于汽車導(dǎo)航系統(tǒng)以及各種應(yīng)急系統(tǒng)，這些系統(tǒng)一般要求到目的地的最佳路線所用時間盡可能短，并且要求根據(jù)交通狀況進(jìn)行實(shí)時計算。經(jīng)典的最短路徑算法——Dijkstra算法是目前多數(shù)系統(tǒng)解決最短路徑問題采用的理論基礎(chǔ)，不同系統(tǒng)對Dijkstra算法采用了不同的實(shí)現(xiàn)方法。本文以經(jīng)典Dijkstra算法為理論基礎(chǔ)，在對矢量地圖進(jìn)行大量分析、實(shí)驗的基礎(chǔ)上，提出最短路徑的一種快速實(shí)現(xiàn)算法，算法的復(fù)雜度與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n成線性關(guān)系，即O（n），與經(jīng)典Dijkstra算法的O（n2）相比，提高了算法的實(shí)用性。

1 ?最短路徑快速實(shí)現(xiàn)算法

1.1 ?經(jīng)典Dijkstra算法的主要思想

Dijkstra算法的基本思路是：假設(shè)每個點(diǎn)都有一對標(biāo)號（dj ， pj），其中dj是從源點(diǎn)s到點(diǎn)j的最短路徑的長度（不包括頂點(diǎn)到其本身）;pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)，k為已標(biāo)記節(jié)點(diǎn)的集合。求解從源點(diǎn)s到點(diǎn)j的最短路徑算法的基本過程如下：

（1）初始化。源點(diǎn)設(shè)置為：ds=0，ps為空;所有其它點(diǎn)：di=∞，pi=？;標(biāo)記源點(diǎn)s，記k ={s}，其他所有點(diǎn)設(shè)為未標(biāo)記。

（2）檢驗從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置：dj=min[dj，dk+lkj]，其中，lkj是從點(diǎn)k到j(luò)的直接連接距離。

（3）選取下一個點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj中最小的一個i：di=min[dj，所有未標(biāo)記的點(diǎn)j]，點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。

（4）找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到i的點(diǎn)j'，作為前一點(diǎn)，設(shè)置：pi= j'。

（5）如果所有點(diǎn)已標(biāo)記，則算法完全退出，否則，記k=k ∪{i}，轉(zhuǎn)到（2）再繼續(xù)。

1.2 ?Dijkstra算法的分析與待改進(jìn)的地方

圖1所示是上海市區(qū)的部分街道圖，其中節(jié)點(diǎn)1為起始點(diǎn)。根據(jù)上一節(jié)描述的Dijkstra算法，當(dāng)計算進(jìn)行到若干次循環(huán)后的情況如圖1所示。其中“◎”表示已標(biāo)記的節(jié)點(diǎn)，“●”表示與已標(biāo)記節(jié)點(diǎn)相鄰的未標(biāo)記節(jié)點(diǎn)。可以看到，此時圖1中節(jié)點(diǎn)1、2本身都已標(biāo)記，并且它們相鄰的節(jié)點(diǎn)也已標(biāo)記。因此形如節(jié)點(diǎn)1、2這種類型的節(jié)點(diǎn)應(yīng)該而且能夠直接跳過算法的第（2）步，從而不做比較。設(shè)已標(biāo)記節(jié)點(diǎn)為m個，其中相鄰節(jié)點(diǎn)中有未標(biāo)記的已標(biāo)記節(jié)點(diǎn)有k個，我們令K={dj|j=1，...，k}，M={dj|j=1，...，m}，則KM。把集合K用平滑曲線連接起來，可以得到一個以起始點(diǎn)為原點(diǎn)的近似圓c，其中集合K中的元素位于圓c的周圍長上，集合M是圓c圍住的所有已標(biāo)記節(jié)點(diǎn)。

圖1 ?道路示意圖

表1、表2是以上海市城區(qū)道路圖數(shù)據(jù)為例的實(shí)驗結(jié)果，從中可以觀察kMax和mMax，和之間的關(guān)系。

表1的幾點(diǎn)說明：所有數(shù)據(jù)的起點(diǎn)相同，終點(diǎn)隨機(jī)選取;kMax、mMax為計算最短路徑時集合K和集合M中元素曾經(jīng)達(dá)到的的最大數(shù)目，和則是集合K和集合M中元素的平均個數(shù);ArcNum為起點(diǎn)到終點(diǎn)沿最短路徑所經(jīng)過的弧段的個數(shù);Distance是起點(diǎn)到終點(diǎn)的實(shí)際距離，單位是m。顯然，弧段的個數(shù)與實(shí)際距離不成正比。

關(guān)于表2的幾點(diǎn)說明：取表1的最后一組數(shù)據(jù)，即kMax=135，mMax=6 756來驗證一次Dijkstra算法計算最短路徑時集合K中元素個數(shù)Knum和集合M中元素個數(shù)Mnum之間的關(guān)系，Knum的采樣間隔大約為10。隨著計算的進(jìn)行，集合K中元素的數(shù)目逐漸增多，集合M中元素的數(shù)目增長的非常快。若干次計算后，集合K、M中的元素數(shù)目分別達(dá)到最大值kMax和mMax。

觀察表1、表2的數(shù)據(jù)，可以得到如下結(jié)論：

（1）隨著起點(diǎn)和終點(diǎn)間距離的增大，kMax、mMax和、都增大，但kMax增長速度遠(yuǎn)小于mMax，增長速度遠(yuǎn)小于。最壞情況下與的比例只有3%左右。

（2）集合K中元素的數(shù)目始終小于集合M中元素的數(shù)目。因此，如果算法中我們只針對集合K進(jìn)行操作，將極大縮小d的規(guī)模，使修改d的時間和在d中選擇最小分量的時間因d的規(guī)模的縮小而降低很多。更進(jìn)一步，如果d是有序的，則從k（k≤kMax）個有序數(shù)中選擇一個最小數(shù)的時間復(fù)雜度為O（1），而從m（m≤mMax）個未排序數(shù)中選擇一個最小數(shù)的時間復(fù)雜度為O（m）。可見，改進(jìn)算法中集合K應(yīng)是有序的。

Dijkstra算法中第（2）、（3）步的計算和比較結(jié)果沒有保存下來，并且每次只選取d中最小的一個，所有沒有選中的未標(biāo)記的節(jié)點(diǎn)在下一次要重新計算dj并查找出一個d中最小的一個。如果把dj保存在每個節(jié)點(diǎn)中，并且把待比較的節(jié)點(diǎn)按序放到一個有序鏈表中，則插入/比較的時間將大大縮短。

根據(jù)圖中頂點(diǎn)和邊的個數(shù)可以求出頂點(diǎn)的平均出度e=m/n（m為邊數(shù)，n為頂點(diǎn)數(shù)），這個數(shù)值代表了圖的連通程度，一般在GIS網(wǎng)絡(luò)圖中，e∈[2，5]，這樣如果當(dāng)前永久標(biāo)記的節(jié)點(diǎn)的出度為t，那么，下一步需掃描的點(diǎn)的個數(shù)就約為0～t個，時間復(fù)雜度降為O（1）。

1.3 ?本文提出的最短路徑快速算法

1.3.1 ?算法描述

所有的節(jié)點(diǎn)分為三種狀態(tài)，即未標(biāo)記（US）、即將標(biāo)記（TS）和已標(biāo)記（AS）三種狀態(tài)。每個節(jié)點(diǎn)都有一對標(biāo)號（dj，pj），其中dj是從源點(diǎn)s到點(diǎn)j的最短路徑的長度（不包括頂點(diǎn)到其本身）;pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。

（1）初始化。①創(chuàng)建TS隊列并清空②標(biāo)記起源點(diǎn)s為AS狀態(tài)③標(biāo)記起源點(diǎn)s的所有出邊點(diǎn)j的狀態(tài)Sj為TS，入TS隊列，其中dj= lsj，TS隊列按照dj的值從小到大有序排列 ④其他所有點(diǎn)設(shè)為US狀態(tài)。

（2）取TS隊列的第一個節(jié)點(diǎn)i（當(dāng)前最小值），標(biāo)記i為AS狀態(tài)，并把i從TS隊列中刪除，若i為終點(diǎn)，轉(zhuǎn)到（5）。

（3）判斷i的所有出邊點(diǎn)j的狀態(tài)：若Sj =US，則dj=di+lij，pj=i，節(jié)點(diǎn)j按dj的大小入TS隊列;否則若Sj=TS，并且dj>di+lij，則dj=di+lij，修改pj=i，節(jié)點(diǎn)j按dj的大小重新排序。

（4）若TS隊列為空，轉(zhuǎn)向（5），否則轉(zhuǎn)到（2）繼續(xù)。

（5）算法結(jié)束。若i為終點(diǎn)，找到最短路徑;否則若TS隊列為空，起點(diǎn)和終點(diǎn)不連通。

1.3.2 ?時間復(fù)雜度分析

由于兩點(diǎn)之間最短路徑的計算次數(shù)隨兩點(diǎn)之間經(jīng)過的節(jié)點(diǎn)數(shù)不同而不同，使得各種輸入集出現(xiàn)的概率難以確定，在這里我們討論算法在最壞情況下的時間復(fù)雜度。整個算法為一重循環(huán)，循環(huán)次數(shù)為n （m最大為n）。算法的循環(huán)體部分是從第（2）到第（4）步，其中第2和4步的時間復(fù)雜度顯然為O（1），關(guān)鍵是分析第（3）步。第（3）步中把i的的所有出邊點(diǎn)依次有序插入TS隊列，其時間復(fù)雜度取決于TS隊列的規(guī)模，設(shè)TS隊列的平均大小為，由以上1.2節(jié)分析可知遠(yuǎn)小于，在最壞情況下，的值大約為115，還是非常小的，因此第（3）步的時間復(fù)雜度為O（）。所以總的時間復(fù)雜度為O（（1+ +1）*n）=O（n），因此本文提出的算法的時間復(fù)雜度僅與節(jié)點(diǎn)數(shù)n成線性關(guān)系，與Dijkstra的時間復(fù)雜度O（n2）相比，效率提高很多。

2 ?改進(jìn)的最短路徑算法的具體實(shí)現(xiàn)

按照以上思路，筆者用Visual C++實(shí)現(xiàn)了上海黃頁最短路徑模塊中最短路徑算法。以上海市區(qū)道路為數(shù)據(jù)（共7 038個節(jié)點(diǎn)，9 365條弧段），計算一條貫穿全城的線路，在普通微機(jī)上約需0.1 s。

2.1 ?數(shù)據(jù)結(jié)構(gòu)的設(shè)計

矢量地圖存儲的方法很多，如鄰接矩陣、鄰接表等。用這些常用的方法存儲交通網(wǎng)絡(luò)，存儲量龐大，而且不利于網(wǎng)絡(luò)操作。文獻(xiàn)[6]提出的以交通節(jié)點(diǎn)為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，雖然克服了上述缺點(diǎn)，但是文獻(xiàn)[6]只考慮節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，對于弧段之間的關(guān)系沒有考慮。而在實(shí)際應(yīng)用中，大多數(shù)GIS網(wǎng)絡(luò)都是有向帶權(quán)圖，如道路有單雙向問題，從一個弧段到其相鄰弧段常有轉(zhuǎn)向限制等。如果我們采用轉(zhuǎn)向表來表示弧段之間的轉(zhuǎn)向關(guān)系，勢必會造成存儲容量激增，并且在計算最短路徑時每一步都要查找轉(zhuǎn)向表，以確定哪個弧段可以轉(zhuǎn)向，造成算法很多不必要的時間開銷。

為了能夠清晰簡單的表示弧段之間的轉(zhuǎn)向關(guān)系，在節(jié)約存儲空間的前提下，本文不采用轉(zhuǎn)向表。在實(shí)現(xiàn)本文提出的算法時，我們把節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系改成弧段和弧段之間的關(guān)系，使道路之間的聯(lián)系更加清晰直接，從而方便計算最短路徑。

我們設(shè)計了兩個類來表示弧段以及弧段之間的聯(lián)系，分別是類CArc和類CArcLink。類CArc包括弧段的狀態(tài)sj，從起源弧段s到弧段j的最短路徑長度dj （包括s和j的長度），起源弧段s到弧段j的最短路徑中j的前一弧段pj，該弧段的權(quán)值（該弧段的長度或耗費(fèi)的時間）;類CArcLink包括弧段之間的轉(zhuǎn)向阻抗，從A弧段能否轉(zhuǎn)向至B弧段的標(biāo)志位（開關(guān)屬性）等。

以下是類CArcLink設(shè)計的主要屬性。

Class CArcLink

{int ?Impedance ; //轉(zhuǎn)向阻抗，如耗費(fèi)時間等//例如30s

bool ?Enabled ; //是否能夠轉(zhuǎn)向，如路口分時段禁行，可設(shè)置此開關(guān)變量//例如1

CNode* ?pNode ; //兩弧段之間的節(jié)點(diǎn)指針//例如節(jié)點(diǎn)1

CArc* pNextArc ; //所連的弧段（出）指針//例如弧段11

};

在圖2所示的道路圖中，弧段1可以轉(zhuǎn)向至弧段6、7和11，但是不可以轉(zhuǎn)向至弧段12。圖2的部分?jǐn)?shù)據(jù)結(jié)構(gòu)示意圖如圖3所示。

圖2 ?道路弧段圖

圖3 ?數(shù)據(jù)結(jié)構(gòu)關(guān)系圖

2.2 ?關(guān)于本文算法實(shí)現(xiàn)的幾點(diǎn)說明

關(guān)于要實(shí)現(xiàn)本文算法的幾點(diǎn)說明如下：

（1）根據(jù)起始點(diǎn)坐標(biāo)確定起始弧段。在最短路徑搜索過程中，定義沿著起點(diǎn)到終點(diǎn)的方向為空間有效方向，相反的方向為空間無效方向。在實(shí)際應(yīng)用中，由于受客觀因素的限制，可能需要在無效方向上的一定距離內(nèi)搜索，因此一般情況下，如果起始路徑是雙向的，則起始弧段有兩條，設(shè)為S1和S2，一并初始化。

（2）本文從減少計算最短路徑時的路徑轉(zhuǎn)向判斷以及降低內(nèi)存耗費(fèi)考慮，取消轉(zhuǎn)向表，單獨(dú)設(shè)置一個時態(tài)參數(shù)表，根據(jù)實(shí)測的交通量可將一天24小時劃分為若干離散時段，各時段不一定等長，以及劃分的時段密度也可以不一致，利用定時器根據(jù)預(yù)先定義的時段來設(shè)置類CArc和類CArcLink的與時態(tài)有關(guān)的屬性，實(shí)現(xiàn)靜態(tài)觸發(fā)修改（經(jīng)驗值修改）。也可以根據(jù)實(shí)測值或者人工智能推理預(yù)測值動態(tài)實(shí)時觸發(fā)修改。

（3）查找最短路徑和查找最小時間耗費(fèi)的問題在理論上是等價的。查找最小時間耗費(fèi)，除了要加上弧段的權(quán)值（該路段上耗費(fèi)的時間），還要加上弧段之間的轉(zhuǎn)向阻抗（轉(zhuǎn)向耗費(fèi)時間），即在改進(jìn)算法的第（3）步，把dj=di+lij修改為dj=di+lij+Iij，其中Iij是從弧段i到弧段j的轉(zhuǎn)向阻抗。

3 ?結(jié) ?語

本文在分析總結(jié)Dijkstra算法的基礎(chǔ)上，對此算法進(jìn)行了改進(jìn)，提出了一個新的最短路徑快速實(shí)現(xiàn)算法，使時間復(fù)雜度由O（n2）降低到O（n）。在算法的實(shí)現(xiàn)上，提出了一種區(qū)別于傳統(tǒng)方法的弧段—弧段存儲結(jié)構(gòu)，使路徑之間的關(guān)系更加清晰直接;把路徑與時態(tài)有關(guān)的屬性信息分開存儲，并通過觸發(fā)器來修改屬性，提高了算法的實(shí)現(xiàn)效率，減小了執(zhí)行算法所需的運(yùn)行空間。本文提出的快速實(shí)現(xiàn)算法已成功的應(yīng)用于上海黃頁基于掌上電腦的電子地圖的最短路徑實(shí)現(xiàn)中，取得了令人滿意的效果。

參考文獻(xiàn)

[1] R.K.Ahuja，K.Mehhorn，J.B.Orlin. Faster Algorithms for the Shorest Path Problem. Technical Report[J]. CS-TR-154—88，Department of Computer Science，Princeton University，1988.

[2] D.P.Bertsekas. The Auction Algorithm for Shortest Path SIAM J[J].Opt.， 1991（1）：425-447.

[3] A.V.Goldberg. Scaling Algorithms for the Shortest Paths Problem[J]. In Proc. 4nd ACM-SIAM Symposium on Discrete Algorithms，Pages 1993：222-231.

[4]樂陽. Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)[J]. 武漢測繪科技大學(xué)學(xué)報，1999，24（3）：209-211.

[5] 韓俊卿.基于GIS的城市道路網(wǎng)最短路徑算法探討[J]. 科技傳播， 2010（8）： 110-111.

[6] 徐業(yè)昌， ?李樹祥， ?朱建民，等. 基于地理信息系統(tǒng)的最短路徑搜索算法[J]. 中國圖象圖形學(xué)報，1998（1）： 43-47.

[7] 陸鋒， 盧冬梅， 崔偉宏. ? 交通網(wǎng)絡(luò)限制搜索區(qū)域時間最短路徑算法[J]. 中國圖象圖形學(xué)報， 1999（10）：47-51.

[8] 陳述彭. 城市化與城市地理信息系統(tǒng)[M].北京：科學(xué)出版社，1999.