GIS中最短路徑的實(shí)現(xiàn)-Read

GIS中最短路徑的實(shí)現(xiàn)張燕，付仲良，黃慶彬本文提出了一種基于矢量角度的最短路徑搜索算法，設(shè)計(jì)出一種類似于面向?qū)ο蟮臄?shù)據(jù)存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)網(wǎng)絡(luò)圖中的節(jié)點(diǎn)及弧段對(duì)象，在最短路徑的搜索上引入矢量夾角標(biāo)量值做為搜索因子，充分利用了網(wǎng)絡(luò)圖中各點(diǎn)元素和線元素間的拓?fù)潢P(guān)系，提高了搜索的趨勢(shì)性，同時(shí)還考慮了各弧段的長(zhǎng)度值（或權(quán)值），較好的將網(wǎng)絡(luò)圖中對(duì)象的空間信息和屬性信息相結(jié)合……1引言隨著地理信息產(chǎn)業(yè)的建立和數(shù)字化信息產(chǎn)品在全世界的普及，地理信息系統(tǒng)將深入到各行各業(yè)甚至各家各戶，成為人們生產(chǎn)、生活學(xué)習(xí)和工作中不可缺少的工具和助手。地理信息系統(tǒng)中網(wǎng)絡(luò)分析功能的主要目的是對(duì)地理網(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è)方面對(duì)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ò)圖：PublicTypeMynode(點(diǎn)結(jié)構(gòu))DimNodelDAsInteger'節(jié)點(diǎn)ID,唯一標(biāo)識(shí)節(jié)點(diǎn)DimAdjoinNumAsInteger'鄰接弧段數(shù)量DimAdjoinArcID()AsInteger'鄰接弧段IDDimAdjoinNodeID()AsInteger'鄰接節(jié)點(diǎn)IDDimAdjoinClamp()AsDouble'指向鄰接節(jié)點(diǎn)的矢量的角度EndTypePublicTypeMyArc(弧結(jié)構(gòu))DimArcIDAsInteger'弧段ID,唯一標(biāo)識(shí)弧段DimLengthAsDouble'弧段長(zhǎng)EndType其中節(jié)點(diǎn)對(duì)象中的三個(gè)數(shù)組大小在初始化時(shí)利用鄰接弧段數(shù)量設(shè)置大小,因此對(duì)應(yīng)不同的節(jié)點(diǎn)對(duì)象其大小是不固定的,使用此種結(jié)構(gòu)，對(duì)于有向圖不會(huì)造成數(shù)據(jù)的冗余，而對(duì)應(yīng)于無向圖也僅多存儲(chǔ)了一倍的弧段ID,鄰接節(jié)點(diǎn)ID及矢量角度，相對(duì)于經(jīng)典Dijkstra算法來說，需要的存儲(chǔ)空間仍較小。對(duì)于弧段對(duì)象來說，其中的Length可以設(shè)置為弧段長(zhǎng)度，也可根據(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è)路線的趨勢(shì)，從概率的角度，順著這個(gè)方向的某些路段的集合組成最短路徑的可能性較大。圖一以矢量夾角標(biāo)量值做為最短路徑頂點(diǎn)選取的第一要素。如圖一，求解A、B兩點(diǎn)間的最短路徑。N1為矢量Aa與矢量AB間夾角的標(biāo)量值，當(dāng)前節(jié)點(diǎn)的每個(gè)鄰接節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)角度標(biāo)量值，按照標(biāo)量值的正負(fù)值大小，構(gòu)造標(biāo)識(shí)分別為正負(fù)的兩個(gè)隊(duì)列，兩個(gè)隊(duì)列均根據(jù)節(jié)點(diǎn)對(duì)應(yīng)標(biāo)量值的絕對(duì)值從小到大進(jìn)行排序。分別從正負(fù)兩個(gè)隊(duì)列中選出排在最前位的節(jié)點(diǎn)，加入到最短路徑樹中。除第一次搜索外，其余過程中都需要判斷搜索到的節(jié)點(diǎn)是否已存在于最短路徑樹中，如果該節(jié)點(diǎn)已存在于最短路徑樹中，則需要比較本次搜索過程結(jié)束后該節(jié)點(diǎn)信息與對(duì)應(yīng)的最短路徑樹節(jié)點(diǎn)信息。假設(shè)在第m次搜索過程中已確定指向節(jié)點(diǎn)S的樹節(jié)點(diǎn)Sm,之后在第n次（n2m）搜索得到的樹節(jié)點(diǎn)Sn再次指向網(wǎng)絡(luò)圖中節(jié)點(diǎn)S。當(dāng)Sn的Length值大于Sm的Length值時(shí)，在Sn處停止搜索，如圖二所示。第1次搜索第?次搜索第的欠搜索IIIII南測(cè)叟索III第盛搜索圖二當(dāng)Sn的Length值小于或等于Sm的Length值，如圖三所示，將Sm之下的所有樹節(jié)點(diǎn)移動(dòng)到Sn之下，并依據(jù)Sn的Length值對(duì)應(yīng)修改原Sm之下所有樹節(jié)點(diǎn)（圖示方框中所有樹節(jié)點(diǎn)）的Length值。

第1次搜索第2次搜索第3出搜索IIIIII第m次搜索II第搜索源點(diǎn)圖三源點(diǎn)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)流程圖如下:

實(shí)現(xiàn)流程圉輸出結(jié)果頸處理：拓?fù)錂z查原節(jié)點(diǎn)衩值較小實(shí)現(xiàn)流程圉輸出結(jié)果頸處理：拓?fù)錂z查原節(jié)點(diǎn)衩值較小在武漢市經(jīng)濟(jì)開發(fā)區(qū)道路圖上任意選取六個(gè)節(jié)點(diǎn)，分別進(jìn)行三次最短路徑求解的實(shí)驗(yàn)，得出的參數(shù)如下表:實(shí)監(jiān)ArcNumberNodeNumberPathLengthModificationTime—本文理法T1225607.5460Dijkstra算法22 ,' 22 '兆口7.523S3'漢1一本文苴法■ 4■ 43157.5:21<1Dijkstra算法4.. 4 ；5157.93036<2二本文尊法111.1配泥石124Dijkstra算法,111.11605-SI其中:ArcNumber表示的是最短路徑經(jīng)過的弧段數(shù)，單位為段;NodeNumber表示的是最短路徑經(jīng)過的結(jié)點(diǎn)個(gè)數(shù)，單位為個(gè);PathLength表示的是最短路徑的長(zhǎng)度，單位為米;Modification在本文算法中表示的是求解過程中樹節(jié)點(diǎn)修改次數(shù)，在Dijkstra算法中表示的是求解過程中節(jié)點(diǎn)標(biāo)號(hào)的修改次數(shù)；Time表示的是求解最短路徑花費(fèi)的時(shí)間，單位為秒。由上表可以看到，在求解最短路徑的過程中本文討論的算法與傳統(tǒng)的Dijkstra算法，最大的差別在于Modification。由于文中探討的算法在求解最短路徑過程中具有起、止點(diǎn)的方向性趨勢(shì)，每次搜索過程中僅考慮當(dāng)前節(jié)點(diǎn)的鄰節(jié)點(diǎn)，故修改次數(shù)較?。欢贒ijksra算法中，每次搜索過程中都將遍歷所有未確定永久標(biāo)號(hào)的節(jié)點(diǎn)，故修改次數(shù)較大。文中探討的算法求解過程簡(jiǎn)單，速度快，求得的最短路徑與用Dijkstra算法求得的最短路徑相同或相近，所以該算法具有一定的實(shí)用性和可操作性。5結(jié)論在對(duì)于搜索技術(shù)性能評(píng)價(jià)的時(shí)候，在各種不同的情況下有著不同的要求，并非只注重最優(yōu)解，而是注重在一定條件下的非劣解。雖然本文討論的算法在道路較不規(guī)整時(shí)求得的最短路徑可能有一定的誤差，但是與