(January 11) http://www.handandaily.com



GIS中最短路徑的實(shí)現(xiàn)
　　　　　　　　　　　　　　　　　　　　
張燕，付仲良 ，黃慶彬

　　1 引言

　　隨著地理信息產(chǎn)業(yè)的建立和數(shù)字化信息產(chǎn)品在全世界的普及，地理信息系統(tǒng)將深入到各行各業(yè)甚至各家各戶，成為人們生產(chǎn)、生活學(xué)習(xí)和工作中不可缺少的工具和助手。

　　地理信息系統(tǒng)中網(wǎng)絡(luò)分析功能的主要目的是對地理網(wǎng)絡(luò)（如交通網(wǎng)絡(luò)）、城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)（如各種網(wǎng)線、電力線、電話線、供排水管線等）進(jìn)行地理分析和模型化。

　　最短路徑問題是地理信息系統(tǒng)網(wǎng)絡(luò)分析中的最基本最關(guān)鍵的問題，在交通網(wǎng)絡(luò)結(jié)構(gòu)的分析，交通運(yùn)輸線路的選擇，通訊線路的建造與維護(hù)，運(yùn)輸貨流的最小成本分析，城市公共交通網(wǎng)絡(luò)的規(guī)劃等，都有直接應(yīng)用的價(jià)值。

　　關(guān)于最短路徑問題，目前為人們所公認(rèn)的最好求解方法，是1959年由E.W.Dijkstar提出的標(biāo)號(hào)法，但具體實(shí)現(xiàn)中在存儲(chǔ)空間及運(yùn)行效率上還存在著一定的問題。

　　本文從圖形數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及最短路徑頂點(diǎn)的搜索策略兩個(gè)方面對Dijkstra算法進(jìn)行了改進(jìn)，提出了一種基于矢量角度的最短路徑搜索算法。

　　2 道路網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)

　　構(gòu)造類似于面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)存儲(chǔ)網(wǎng)絡(luò)圖：

　　Public Type Mynode（點(diǎn)結(jié)構(gòu)）

　　　　Dim NodeID As Integer '節(jié)點(diǎn)ID，唯一標(biāo)識(shí)節(jié)點(diǎn)

　　　　Dim AdjoinNum As Integer '鄰接弧段數(shù)量

　　　　Dim AdjoinArcID() As Integer '鄰接弧段ID

　　　　Dim AdjoinNodeID() As Integer '鄰接節(jié)點(diǎn)ID

　　　　Dim AdjoinClamp() As Double '指向鄰接節(jié)點(diǎn)的矢量的角度

　　End Type

　　Public Type MyArc（弧結(jié)構(gòu)）

　　　　Dim ArcID As Integer '弧段ID，唯一標(biāo)識(shí)弧段

　　　　Dim Length As Double '弧段長

　　End Type

　　其中節(jié)點(diǎn)對象中的三個(gè)數(shù)組大小在初始化時(shí)利用鄰接弧段數(shù)量設(shè)置大小，因此對應(yīng)不同的節(jié)點(diǎn)對象其大小是不固定的，使用此種結(jié)構(gòu)，對于有向圖不會(huì)造成數(shù)據(jù)的冗余，而對應(yīng)于無向圖也僅多存儲(chǔ)了一倍的弧段ID，鄰接節(jié)點(diǎn)ID及矢量角度，相對于經(jīng)典Dijkstra算法來說，需要的存儲(chǔ)空間仍較小。對于弧段對象來說，其中的Length可以設(shè)置為弧段長度，也可根據(jù)需要設(shè)置為時(shí)間、費(fèi)用等相應(yīng)的權(quán)值。

　　3 算法原理

　　由兩點(diǎn)之間直線最短的定理，構(gòu)造一條理想最短路徑（如圖一中的AB），這條直線段一定是A、B兩點(diǎn)間弧段中距離最短的一條。但實(shí)際上這條直線段作為一段道路存在的可能性極小，但這條從起點(diǎn)到終點(diǎn)的直線段卻代表了一個(gè)路線的趨勢，從概率的角度，順著這個(gè)方向的某些路段的集合組成最短路徑的可能性較大。

　　　　　　　　　　　　　　　　　　

　　以矢量夾角標(biāo)量值做為最短路徑頂點(diǎn)選取的第一要素。

　　如圖一，求解A、B兩點(diǎn)間的最短路徑。∠1為矢量Aa與矢量AB間夾角的標(biāo)量值，當(dāng)前節(jié)點(diǎn)的每個(gè)鄰接節(jié)點(diǎn)都對應(yīng)一個(gè)角度標(biāo)量值，按照標(biāo)量值的正負(fù)值大小，構(gòu)造標(biāo)識(shí)分別為正負(fù)的兩個(gè)隊(duì)列，兩個(gè)隊(duì)列均根據(jù)節(jié)點(diǎn)對應(yīng)標(biāo)量值的絕對值從小到大進(jìn)行排序。

　　分別從正負(fù)兩個(gè)隊(duì)列中選出排在最前位的節(jié)點(diǎn)，加入到最短路徑樹中。

　　除第一次搜索外，其余過程中都需要判斷搜索到的節(jié)點(diǎn)是否已存在于最短路徑樹中，如果該節(jié)點(diǎn)已存在于最短路徑樹中，則需要比較本次搜索過程結(jié)束后該節(jié)點(diǎn)信息與對應(yīng)的最短路徑樹節(jié)點(diǎn)信息。

　　假設(shè)在第m次搜索過程中已確定指向節(jié)點(diǎn)S的樹節(jié)點(diǎn)Sm，之后在第n次（n ≥ m）搜索得到的樹節(jié)點(diǎn)Sn再次指向網(wǎng)絡(luò)圖中節(jié)點(diǎn)S。

　　當(dāng)Sn的Length值大于Sm的Length值時(shí)，在Sn處停止搜索，如圖二所示。

　　　　　　　　　　

　　當(dāng)Sn的Length值小于或等于Sm的Length值，如圖三所示，將Sm之下的所有樹節(jié)點(diǎn)移動(dòng)到Sn之下，并依據(jù)Sn的Length值對應(yīng)修改原Sm之下所有樹節(jié)點(diǎn)（圖示方框中所有樹節(jié)點(diǎn)）的Length值。

　　　　　　　　　　

　　4 算法實(shí)現(xiàn)

　　本算法在武漢市經(jīng)濟(jì)開發(fā)區(qū)道路網(wǎng)絡(luò)圖上得到實(shí)現(xiàn)。武漢市經(jīng)濟(jì)開發(fā)區(qū)道路網(wǎng)絡(luò)圖中共有節(jié)點(diǎn)371個(gè)，邊653條。在ArcMap的VBA環(huán)境中，通過VB＋ArcObjects的編程方式，由VB實(shí)現(xiàn)算法邏輯控制，ArcMap管理圖形的顯示與控制，實(shí)現(xiàn)在圖形窗口中動(dòng)態(tài)顯示求得的最短路徑以及選取組成最短路徑的路段集合的過程。實(shí)現(xiàn)流程圖如下：

　　　　　　　　　　　　

　　在武漢市經(jīng)濟(jì)開發(fā)區(qū)道路圖上任意選取六個(gè)節(jié)點(diǎn)，分別進(jìn)行三次最短路徑求解的實(shí)驗(yàn)，得出的參數(shù)如下表：

　　
　 　其中：

　　Arc Number表示的是最短路徑經(jīng)過的弧段數(shù)，單位為段；

　　Node Number表示的是最短路徑經(jīng)過的結(jié)點(diǎn)個(gè)數(shù)，單位為個(gè)；

　　Path Length表示的是最短路徑的長度，單位為米；

　　Modification在本文算法中表示的是求解過程中樹節(jié)點(diǎn)修改次數(shù)，在Dijkstra算法中表示的是求解過程中節(jié)點(diǎn)標(biāo)號(hào)的修改次數(shù)；

　　Time表示的是求解最短路徑花費(fèi)的時(shí)間，單位為秒。

　　由上表可以看到，在求解最短路徑的過程中本文討論的算法與傳統(tǒng)的Dijkstra算法，最大的差別在于Modification。

　　由于文中探討的算法在求解最短路徑過程中具有起、止點(diǎn)的方向性趨勢，每次搜索過程中僅考慮當(dāng)前節(jié)點(diǎn)的鄰節(jié)點(diǎn)，故修改次數(shù)較小；而在Dijksra算法中，每次搜索過程中都將遍歷所有未確定永久標(biāo)號(hào)的節(jié)點(diǎn)，故修改次數(shù)較大。

　　文中探討的算法求解過程簡單，速度快，求得的最短路徑與用Dijkstra算法求得的最短路徑相同或相近，所以該算法具有一定的實(shí)用性和可操作性。

　　5 結(jié)論

　　在對于搜索技術(shù)性能評價(jià)的時(shí)候，在各種不同的情況下有著不同的要求，并非只注重最優(yōu)解，而是注重在一定條件下的非劣解。雖然本文討論的算法在道路較不規(guī)整時(shí)求得的最短路徑可能有一定的誤差，但是與最短路徑的最優(yōu)解相近，而非劣解，且在其他情況下都能求得最優(yōu)解，求解的速度快，故具有一定的實(shí)用性和可操作性。

　　由于實(shí)際情況的復(fù)雜性，為了減小算法在求解時(shí)產(chǎn)生的誤差，使得算法有更好的適應(yīng)性，有進(jìn)一步研究道路網(wǎng)絡(luò)圖中拓?fù)潢P(guān)系的必要，增加矢量條件，真正使最短路徑的求解過程簡單快速，結(jié)果準(zhǔn)確可信。