基于城市路網(wǎng)的最短路徑算法研究

戴建光

(常州市武進(jìn)規(guī)劃與測繪院，江蘇 常州 213159)

基于城市路網(wǎng)的最短路徑算法研究

戴建光*

(常州市武進(jìn)規(guī)劃與測繪院，江蘇 常州 213159)

最短路徑分析是城市路網(wǎng)分析的重要內(nèi)容之一，本文分析了幾種流行的最短路徑算法，通過對比其優(yōu)缺點，得出A*算法比較適合城市路網(wǎng)最短路徑分析的結(jié)論?；诔Ｖ菔形溥M(jìn)城區(qū)路網(wǎng)數(shù)據(jù)對A*算法進(jìn)行測試，試驗結(jié)果表明，在時間效率和準(zhǔn)確性方面，A*算法都符合城市路網(wǎng)最短路徑分析的要求。

城市路網(wǎng)；最短路徑算法；A*算法

1 引 言

城市化的發(fā)展和城市道路的不斷建設(shè)，給人們的生活帶來了很大便利，同時城市路網(wǎng)也變得越來越龐大與復(fù)雜，對城市路網(wǎng)的分析與利用成為人們密切關(guān)注的問題之一。GIS因其強(qiáng)大的網(wǎng)絡(luò)分析功能在城市路網(wǎng)研究中發(fā)揮了重要作用，而路網(wǎng)分析中最基本、最關(guān)鍵的問題是最短路徑問題，最短路徑分析就是如何在最短的時間內(nèi)花費(fèi)最少的代價到達(dá)目的地。由于最短路徑分析在實際中常用于導(dǎo)航、火警、醫(yī)療等應(yīng)急系統(tǒng)，這類系統(tǒng)對最短路徑算法的時間要求比較高(一般要求在 1 s～3 s)，同時在行駛過程中還要求實時計算行駛路線，這就決定了最短路徑算法必須是高效率的。

2 主流算法比較

目前國內(nèi)外針對最短路徑的算法主要有單源點最短路徑算法Dijkstra算法、全源最短路徑算法Floyd算法、啟發(fā)式搜索算法A*算法等。下面重點研究討論 Dijkstra算法、Floyd算法、A*算法的原理和三者的對比分析。

2.1 Dijkstra算法

Dijkstra算法是1959年由荷蘭計算機(jī)學(xué)家Dijkstra提出的，它是從一個節(jié)點到其余各節(jié)點之間的最短路徑算法，主要特點是以起始點為中心向外層層擴(kuò)展，直到到達(dá)目標(biāo)點為止。假設(shè)起始節(jié)點為s，目標(biāo)節(jié)點為t，路網(wǎng)中每個節(jié)點的標(biāo)號為(di，pi)，di是從起始點s到點i的最短路徑長度，pi是從s到i最短路徑中i點的前一點，w(k，j)表示點i到點j的距離。算法基本步驟如下：

Step 1：所有節(jié)點初始化。起始點ds=0，ps=null，標(biāo)記起始點，k=s，其他點di=∞，pi=null，均設(shè)置為未標(biāo)記。

Step 2：計算所有已標(biāo)記的點k到未標(biāo)記的點j的距離，設(shè)置dj=min[dj，dk+w(k，j)]。

Step 3：從未標(biāo)記的點中選取距離最小的點i，從標(biāo)記的點中查找與i點直接相連的節(jié)點，記pi。設(shè)置點i為已標(biāo)記，并記錄為最短路徑中的一點。

Step 4：繼續(xù)分析，直至所有點都被標(biāo)記，算法結(jié)束。

從上述步驟中可以看出，Dijkstra算法的時間復(fù)雜度為O(n2)(n為路網(wǎng)中的節(jié)點個數(shù))，而且如果想得到任意兩個節(jié)點之間的最短路徑，則需要每次以一個節(jié)點為起始點，重復(fù)運(yùn)算n次，則相應(yīng)的時間復(fù)雜度就變成了O(n3)。因為Dijkstra算法計算的是起始點到其他所有節(jié)點的最短路徑，因此它的時間復(fù)雜度比較高，相應(yīng)的效率較低。

2.2 Floyd算法

Floyd算法是由Floyd提出的，它是通過一個圖的權(quán)值矩陣求出每兩點間的最短路徑矩陣。算法思路是從任意一條單邊路徑開始，兩點間相連時以邊長定權(quán)，不相連權(quán)設(shè)為無窮大。然后對于每一對節(jié)點u和v，判斷是否有節(jié)點w使得u-w-v的距離比u-v的距離短，如果有，則更新矩陣。算法基本步驟如下：

Step 2：設(shè)k=0，權(quán)陣D(0)=D。

Step 3：設(shè)k=k+1，計算：

D(k)=(dij(k))m×n，k=1，2，…，n

其中：dij(k)=min[dij(k-1)，dik(k-1)+dkj(k-1)]。

Step 4：重復(fù)運(yùn)算，直至k=n完成最短路徑分析。

如果需要保留路徑信息，要在運(yùn)算中保留下標(biāo)信息，即dik+dkj=dikj，或者在運(yùn)算時將路徑信息保存在path矩陣中。

從上述步驟中可以看出，F(xiàn)loyd算法的時間復(fù)雜度為O(n3)(n為路網(wǎng)中的節(jié)點個數(shù))，時間復(fù)雜度依然較高，對于城市路網(wǎng)的最短路徑分析效率較低。

2.3 A*算法

A*算法是由Hart、Nilsson、Raphael等首先提出的一種啟發(fā)式搜索算法，該算法在搜索過程中加入啟發(fā)因子來縮小搜索范圍，從而加快搜索速度。該算法的公式表示為f(n)=g(n)+h(n)，其中，f(n) 是從初始點經(jīng)由節(jié)點n到目標(biāo)點的估價函數(shù)，g(n) 是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n) 是從n到目標(biāo)節(jié)點最佳路徑的估計代價。算法基本步驟如下：

Step 1：創(chuàng)建兩個表，其中open表存放所有已生成但是還未分析的點，close表存放已經(jīng)分析的點。

Step 2：計算起始點s的估價值，并放入open表，按照估價值f將open表中的節(jié)點排序(最小的在最前面)，從open表中取出估價值f最小的節(jié)點n(第一次取得點為起始點)。

Step 3：對取出節(jié)點n的所有子節(jié)點k進(jìn)行分析：如果k在open表中，判斷k的估價值是否小于open表的估價值，如果是，把n設(shè)置為X的父節(jié)點，更新open表中的估價值；如果k在close表中，繼續(xù)分析下一個子節(jié)點；如果既不在open表也不在close表中，把n設(shè)置為k的父節(jié)點，求出k的估價值f(k)，并將k插入open表中。

Step 4：將n節(jié)點插入close表中，對open表中的節(jié)點重新排序。

Step 5：重復(fù)步驟2～4，直至取出的節(jié)點為目標(biāo)節(jié)點，最短路徑分析完成。

從上述步驟中可以看出，A*算法得出的路徑可能不是最短的路徑，但是該算法除了考慮起始點到該節(jié)點的距離，還對節(jié)點到終點的距離進(jìn)行了估價，這樣避免了盲目的搜索，大大縮小了搜索范圍，提高了算法的效率，因此針對城市路網(wǎng)，尤其是移動端的城市路網(wǎng)最短路徑分析，A*算法有著明顯的優(yōu)勢。

3 實驗驗證

為了驗證A*算法是否能在城市路網(wǎng)的最短路徑分析中起到實際作用，文章選擇了江蘇省常州市武進(jìn)區(qū)的一塊路網(wǎng)數(shù)據(jù)(約850個路節(jié)點)，如圖1所示。

圖1 實驗區(qū)域路網(wǎng)概況圖

用java語言在三星平板電腦上開發(fā)了Dijkstra算法、Floyd算法和A*算法，分別計算實驗路網(wǎng)的最短路徑，得到的時間效率對比結(jié)果如表1所示。

Dijkstra算法、Floyd算法、A*算法時間效率對比 表1

為了驗證A*算法最短路徑計算結(jié)果的準(zhǔn)確性，程序還接入了百度地圖的路徑查詢功能接口以供對比分析，對比結(jié)果如圖2、圖3所示。

通過和百度地圖的路徑查詢功能接口的對比，可以看出，基于A*算法的最短路徑分析結(jié)果和百度地圖分析結(jié)果基本一致，而在運(yùn)行時間上也相差不多，可以滿足城市路網(wǎng)的最短路徑分析需求。

圖2 百度地圖路徑計算結(jié)果(用時198 ms)

圖3 A*算法計算結(jié)果(用時235 ms)

4 總 結(jié)

文章通過Dijkstra算法、Floyd算法、A*算法的對比分析，體現(xiàn)了A*算法的時間效率優(yōu)勢并通過實例證明，同時通過與百度地圖路徑分析功能的對比，驗證了A*算法最短路徑分析結(jié)果的準(zhǔn)確性。通過實際的城市路網(wǎng)數(shù)據(jù)測試，A*算法在城市路網(wǎng)數(shù)據(jù)最短路徑分析中，效率和準(zhǔn)確性方面都取得了比較滿意的成果。

[1] 王開義，趙春江，胥桂仙，宋曉宇. GIS領(lǐng)域最短路徑搜索問題的一種高效實現(xiàn)[J]. 中國圖像圖形學(xué)報，2003，8(8)：951～956.

[2] 吳必君，李利新，雷小平. 基于城市道路數(shù)據(jù)庫的最短路徑搜索[J]. 西南交通大學(xué)學(xué)報，2003，38(1)：80～83.

[3] 王肖，徐友春，章永進(jìn)等. 一種基于GIS最短路徑搜索的A*改進(jìn)算法[J]. 計算機(jī)系統(tǒng)應(yīng)用，2008，5：28～31.

[4] 陳波，楊陽，鄭文軍. 一種基于道路網(wǎng)分層的最短路徑算法[J]. 海洋測繪，2006，26(3)：21～23.

[5] 唐一行. 論Floyd最短路徑算法在火災(zāi)消防救援中的應(yīng)用[J]. 現(xiàn)代商貿(mào)工業(yè)，2010，24：383～384.

[6] 朱凱. 應(yīng)用于公交網(wǎng)絡(luò)交通中最短路徑算法的研究[J]. 信息技術(shù)，2012，11(5)：186～188.

[7] 王榮，江東，韓惠. 基于Floyd方法的最短路徑算法優(yōu)化算法[J]. 甘肅科學(xué)學(xué)報，2012，24(4)：110～114.

Shortest Path Algorithm Based on City Road Network Study

Dai Jianguang

(Changzhou Wujin Planning and Surveying Institute，Changzhou 213159，China)

shortest path analysis is an important part of city road network analysis，this paper analyzed several popular Shortest path algorithm，we got a conclusion that A* algorithm is more suitable for city road network analysis by comparing their strength and weaknesses. Finally the A* algorithm is tested based on Wujin road network data，the test result showed that A* algorithm can meet the requirement of city road network analysis.

city road network；shortest path algorithm；A* algorithm

1672-8262(2016)06-47-03

P208.2，TP391

A

2016—11—08

戴建光(1973—)，男，碩士，高級工程師，從事城市規(guī)劃與3S技術(shù)應(yīng)用工作。

2016年度江蘇省測繪地理信息科研項目(JSCHKY201615)