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

戴建光

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

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

戴建光*

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

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

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

1 引 言

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

2 主流算法比較

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

2.1 Dijkstra算法

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

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

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

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

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

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

2.2 Floyd算法

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

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

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

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)算時(shí)將路徑信息保存在path矩陣中。

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

2.3 A*算法

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

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

圖1 實(shí)驗(yàn)區(qū)域路網(wǎng)概況圖

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

Dijkstra算法、Floyd算法、A*算法時(shí)間效率對(duì)比 表1

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

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

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

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

4 總 結(jié)

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

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

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

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

[4] 陳波，楊陽(yáng)，鄭文軍. 一種基于道路網(wǎng)分層的最短路徑算法[J]. 海洋測(cè)繪，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é)報(bào)，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—)，男，碩士，高級(jí)工程師，從事城市規(guī)劃與3S技術(shù)應(yīng)用工作。

2016年度江蘇省測(cè)繪地理信息科研項(xiàng)目(JSCHKY201615)