淺談GIS中網絡分析與最短路徑的實現

1、交通 GIS 及應用課程論文I淺談 GIS 中網絡分析與最短路徑的實現專業(yè)：交通信息工程及控制本科生：程海峰主導老師：林科摘摘 要要網絡分析作為 GIS 的重要功能在電子導航、交通管理、城市規(guī)劃、管線的布局設計中發(fā)揮了重要的作用。本文側重于從網絡拓撲關系的獲取到最短路徑算法的實現，為進一步研究 GIS 中網絡分析的高效訪問奠定基礎。文章首先介紹了網絡拓撲數據模型的一些基本概念，根據已有的研究經驗，提出了自己有關網絡數據模型中最基本的兩個概念（網線和結點）的理解。在這個框架之下，又分析了網絡拓撲關系的建立過程，得出了網絡拓撲關系獲取的一般過程。第二部先介紹了最短路徑算法選擇的有關問題，通過查閱有

2、關文獻發(fā)現，目前解決系統最短路徑問題應用最為廣泛的是 Dijkstra 算法的思想。最后闡述了有關經典 Dijkstra 算法的主要思想并利用有關數據結構方面的知識寫出了具體算法的實現過程。關鍵詞：網絡拓撲關鍵詞：網絡拓撲 網絡數據模型網絡數據模型 Dijkstra 算法算法 交通 GIS 及應用課程論文II目目 錄錄摘 要 .I1. 引 言 .- 1 -2. 網絡拓撲關系的建立 .- 2 -2.1 網絡數據模型的基本概念.- 2 -2.2 網絡拓撲關系的獲取.- 2 -3. 最短路徑算法.- 5 -3.1 算法選擇.- 5 -3.2 傳統 DIJKSTRA算法的主要思想 .- 5 -3.3

3、經典 DIJKSTRA算法的實現 .- 6 -參考文獻 .- 8 -附 錄 .- 9 -交通 GIS 及應用課程論文- 1 -1. 引 言隨著地理信息系統產業(yè)的建立和數字化信息產品在全世界的普及，地理信息系統已經深入到各行各業(yè)。其中，網絡分析是地理信息系統（GIS）最主要的功能之一。對地理網絡（如交通網絡） 、城市基礎設施網絡（如各種網線、電力網線、電話網線、供排水網線等）進行地理分析和模型化，是地理信息系統中網絡分析的主要目的。近幾年來面向社會的 GIS 應用開發(fā)不斷增多,逐漸形成以 MapObject 和 MapGuide 為主流的GIS 應用開發(fā)體系，但這兩個系統都沒有現成的網絡分析功能

4、,只有通過二次開發(fā)才能實現 MapObject 和 MapGuide 的網絡分析功能。 】【1 網絡分析中最基本最關鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短,還可以引申到其他的度量,如時間、費用、線路容量等。相應地,最短路徑問題就成為最快路徑問題、最低費用問題等。其實,無論是距離最短、時間最快還是費用最低,它們的核心算法都是最短路徑算法。 最短路徑的求解,必須把現實生活中的道路、管線等各種網絡抽象成一種數學結構,這種抽象出來的數學結構被稱為網絡拓撲結構。于是各種網絡分析技術實現的關鍵在于網絡拓撲結構的建立和高效能最短路徑算法。下面我就分別從這兩方面討論起。 交通 GIS

5、 及應用課程論文- 2 -2. 網絡拓撲關系的建立網絡拓撲關系的建立網絡分析是空間分析的一個重要方面，是依據網絡拓撲關系（線性實體之間、線性實體與結點之間、結點與結點之間的連結、聯通關系） ，并通過考察網絡元素的空間、屬性數據，對網絡的性能特征進行多方面的分析計算。對地理網絡、城市基礎設施】【2網絡進行地理分析和模型化的關鍵技術是用什么樣的方式抽象出網絡拓撲結構,及節(jié)點與節(jié)點的連通關系,并對網絡拓撲結構進行高效能訪問。2.1 網絡數據模型的基本概念網絡數據模型的基本概念網絡是由若干線性實體互連而成的一個系統，資源由網絡來傳輸，實體間的聯絡也由網絡來達成。網絡數據模型是真實世界中網絡系統（如交通

6、網、通訊網、自來水網等）的抽象表示。構成網絡的基本元素是上述線性實體以及這些實體的連結交匯點。前者被稱為網線或鏈（link） ，后者一般稱為結點（node） 。網線構成網絡的骨架，】【3是資源傳輸或通訊網絡的通道，可以代表公路、鐵路、航線、水管、河流等；結點是網線的端點，又是網線的交匯點，可以表示交叉路口、中轉站、河流匯合點等。除了上述基本網絡元素之外，網絡還可能有若干附屬元素，如在路徑分析中用來表示途徑地點的站點；在資源分配中用來表示資源發(fā)散地點或資源匯聚地點的中心；對資源傳輸或通訊網絡起阻斷作用的障礙等。針對網絡分析的需要，作為網絡基本元素的網線或結點除自身的常規(guī)屬性外，還要具有一些特殊屬

7、性的數據。比如，為了實施路徑分析和資源分配，網線數據應包含正反兩個方面上的阻礙度以及資源需求量，而節(jié)點數據也應該包含資源需求量。2.2 網絡拓撲關系的獲取網絡拓撲關系的獲取GIS 中的數據(如道路、管網、水系等)要進行最短路徑的計算,就必須首先將其按結點和邊的關系抽象為圖的結構,這在 GIS 中稱為構建網絡的拓撲關系。只有建立了拓撲關系,我們才能進行網絡路徑分析。在 GIS 系統拓撲數據結構中，通常具有如下三種重要的拓撲形式：說明線串如何相連的連通性，即線串是在結點上相互連接的。多邊形是由一系列相連通的線串組成的。記錄多邊形的相鄰信息已表示拓撲結構的連續(xù)性是根據線串的走向，可以決定誰是左多邊形

8、。同時，量多變形之所以相鄰是因為二者具有共同的邊界。交通 GIS 及應用課程論文- 3 -為了能夠更好的描述路網拓撲結構的建立過程，首先介紹一下描述路網的基本要素及各要素的屬性。描述路網的基本要素：點對象：路網中道路和道路的交叉點以及道路的端點。先對象：用弧或鏈表示路段，形成路段的基本規(guī)則是：道路的所有車道合在一起，兩結點之間的部分形成一個路段。面對像：有路段線圍成的封閉區(qū)域。相關路網要素的屬性：路段標識符（用編號表示） 起、終點標識符（用編號表示）路段名稱路段長度道路類別結點表示符號結點坐標通常，可以用賦權圖來表示路網。具體做法是分別存儲點狀實體 結點，線狀實體兩點間的路段，結點和路段的屬性

9、信息，以及實體間的拓撲關系（主要是連通性和方向性） 。這樣從圖論的角度看，便將路網轉化為一個圖。進一步還可以在每一條邊上定義權，這樣便得到了一個賦權圖。從而，確定某兩地間的最優(yōu)路線問題便可以轉化為在賦權圖上求兩點間的最短路徑問題。對于矢量圖形的拓撲關系的描述，主要有基于網路的拓撲模型和基于點集拓撲理論的拓撲模型?；诰W絡的拓撲模型具有直觀、結構清晰、互換性強、便于組織存】【4儲等優(yōu)點。路網拓撲關系主要討論線與線之間的聯通性關系，即將其按結點和邊的關系抽象為圖的結構，這在 GIS 中稱為構建網絡的拓撲關系，在計算機中這種拓撲關系與面無關，拓撲關系中只記錄了線與結點的關系，而沒有線與面的關系，所以

10、不是完備的拓撲關系。路網拓撲結構主要包括兩種對象，結點（Node）對象和邊（Link）對象。結點對象主要包括結點序號，結點屬性和它附近的相關信息，及與之相連接的編序號；邊對象應包括編序號，長度信息，兩個端點序號。根據結點對象相連接的邊序號和邊對象的兩個端點序號，就建立了結點之間的連接特性。路網的拓撲結構的生成主要找出各路段之間的直接連通性，實現算法是找出相應圖層中的所有線圖元，然后判斷任意兩線圖元是否相交，根據交點和頂點得到結點，根據橡膠關系判斷兩條邊是否直接相連接，再根據相關信息對相應邊賦權值，利用拓撲得到的帶權圖來查詢最短路徑。拓撲結構的建立過程表示為圖 2.1 的流程圖。交通 GIS 及

11、應用課程論文- 4 -圖 2.1 拓撲關系建立過程流程圖交通 GIS 及應用課程論文- 5 -3. 最短路徑算法最短路徑算法 由于網絡特征的復雜性和問題的不同特征，最短路徑的算法也表現出多樣性。但總的來說可以按問題的類型、網絡特征和實現的算法進行分類，其中最經典，應用最廣泛的的還是 Dijkstra 算法。在實際應用當中，應該根據不同問題的類型選擇適合于該問題的算法。3.1 算法選擇算法選擇最短路徑算法選取的原則一般包括：1.算法速度快；2.算法占用資源少；3.算法穩(wěn)定性強。據統計，目前提出來的最短路徑算法大約有 17 種，F.BenJiama 等人對其中的15 種進行了測試，結果顯示有三種效

12、果比較好，他們分別是 TQQ（graph growth with to queues） 、DKA（the Dijkstras algorithm with approximate buckets） 、以及 DKD（the Dijkstras implemented with double buckets） 。其中 TQQ 算法的基礎是圖增長理論，較適合于單點到其他各點的最短距離；后兩種算法則都是基于 Dijkstra 的算法，較適合于計算兩點間最短距離。目前多數系統解決最短路徑問題采用的是 Dijkstra 算法為理論】【5基礎,只是不同系統對 Dijkstra 算法采用了不同的實現方法。針對

13、不同的網絡特征、應用需求及具體的硬件環(huán)境，各種算法在時間復雜度、空間復雜度、實的難易程度等方面各具特色。3.2 傳統傳統 Dijkstra 算法算法的主要思想的主要思想Dijkstra 算法的基本思路是：假設每個頂點都有一對標號，其中是從起），（jjpdjd點 s 到終點 j 的最短路徑長度；則是從 s 到 j 的最短路徑中 s 的前一點。求解從 s 到jpj 的最短路徑的算法的基本過程如下：初始化。起始點設置為：，為空；所有其它點：，=？；0dsjpidip標記起始點 s，計 k=s，其它所有點設為為標記的。檢驗從所有以標記的點 k 到其直接連接的標記點 j 的距離，并設置： ,minkjk

14、jjlddd 式中，是從點 k 到 j 的直接連接距離。kjl交通 GIS 及應用課程論文- 6 -選取下一個點。從所有為標記的結點中，選取中最小的一個 i：jd minjddji，所有未標記的點 點 i 就被選為最短路徑中的一點，并設為以標記的。找到點 i 的前一點。從以標記的點中找到直接連接到點 i 的點，作為前一點，設*j置： *ji 標記點 i。如果所有點以標記，則算法完全退出，否則，記 k=i，轉到 2）在繼續(xù)。3.3 經典經典 Dijkstra 算法的實現算法的實現首先，引進一個輔助向量 D，它的每個分量 D 表示當前所找到的從始點 v 到每個終點 vi 的最短路徑的長度。如 D3

15、=2 表示從始點 v 到終點 3 的路徑相對最小長度為2。這里強調相對就是說在算法過程中 D 的值是在不斷逼近最終結果但在過程中不一定就等于最短路徑長度。它的初始狀態(tài)為：若從 v 到 vi 有弧，則 D 為弧上的權值；否則置 D 為。顯然，長度為 Dj=MinD | viV 的路徑就是從 v 出發(fā)的長度最短的一條最短路徑。此路徑為(v,vj)。 那么，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是 vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從 v 到 vk 的弧上的權值，或者是 Dj和從 vj 到 vk 的弧上的權值之和。 一般情況下，假

16、設 S 為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（設其終點為 X）或者是弧(v,x)，或者是中間只經過 S 中的頂點而最后到達頂點 X 的路徑。因此，下一條長度次短的最短路徑的長度必是 Dj=MinD | viV-S 其中，D 或者是弧(v,vi)上的權值，或者是 Dk(vkS)和弧(vk,vi)上的權值之和。 迪杰斯特拉算法描述如下： 1）arcs 表示弧上的權值。若不存在，則置 arcs 為（在本程序中為 MAXCOST） 。S 為已找到從 v 出發(fā)的最短路徑的終點的集合，初始狀態(tài)為空集。那么，從 v 出發(fā)到圖上其余各頂點 vi 可能達到的最短路徑長度的初值為 D=arcsL

17、ocate Vex(G,v),i viV 2）選擇 vj，使得 Dj=MinD | viV-S 3）修改從 v 出發(fā)到集合 V-S 上任一頂點 vk可達的最短路徑長度下面為用 C 語言描敘的迪杰斯特拉算法：void ShortestPath_DIJ(MGraph G，int v0， PathMatrix &P，ShortPathtable &D) 交通 GIS 及應用課程論文- 7 -/用 Dijkstra 算法求有向圖 G 的 v0 頂點到其余 v 的最短路徑 Pv及其帶權長度DV /若 Pvw為 true,那么 w 是從 v0 到 v 當前求得最短路徑上的點 /finalv

18、為 true 當且僅當 v 屬于 s，即已經求得從 v0 到 v 的最短路徑 for(v=0；v G.vexnum；v+) finalv=false；Dv=G.arcsv0v；for(w=0；w G.vexnum；w+) Pvw=false； /設置空路徑 if(Dv infinity) Pvv0=true；Pvv=true； Dv0=0;finalv0=true；/開始主循環(huán)，每次求得 v0 到某個 v 定點的最短路徑，并且加 v 入到 s 集 for(i=1；i G.vexnum；i+) min=infinity； /infinity 是無窮的大數 for(w=0；w G.vexnum；w

19、+) if(!finalw) if(Dw min) v=w；min=Dw；finalv=true；for(w=0；w G.vexnum；w+) /更新當前最短路徑和距離if(!finalw & (min+G.arcsvw) Dw) Dw=min+G.arcsvw；Pw=Pv;； Pww=true； 交通 GIS 及應用課程論文- 8 - 交通 GIS 及應用課程論文- 9 -參考文獻參考文獻1胡明光、張亮：GIS 網絡分析功能的實現J, 科教文匯2007 年9 月下旬刊。2Michael N.DeMers.武法東、付宗棠等譯: 地理信息系統基本原理M,電子工業(yè)出版社，2001 年第二版

20、，第 45-47 頁。3張榮梅：智能交通地理信息系統的設計與實現J, 計算機應用研究2000 年第一期，第 97-98 頁。4王行風、賈凌：GIS 支持下的城市交通網絡最短路徑研究J ， 計算機與現代化2005 年第四期，第 9-12 頁。5F B ZHAN. Three fastest Path Algorithms on Real Road NetworksJ, Journal of Geographic Information and Decision Analysis ， 1997，1（2）：56-57。交通 GIS 及應用課程論文- 10 -附附 錄錄下面是一個有關用鄰接矩陣實現的一

21、個簡單 C 程序#include#include#define MAX 10/p:二維數組，存放權值 /n:頂點個數/di:i 距離出發(fā)點的最短路徑/pathi:最短路徑上 i 前面頂點的編號/s:出發(fā)點 void shortestPath(int p8, int n, int d, int path, int s) /判斷出發(fā)點有沒有鄰接點 for(int i=0; in; +i) if( psi != MAX) break; else if(i = n) return; /頂點 v 是否并入集合 S 中； bool isUnionn; /初始化 for(int i=0; in; +i) d

22、i = MAX; pathi = -1; isUnioni = false; /初始化出發(fā)點相鄰接的頂點距離 for(int i =0; in; +i) if(psi != MAX) di = psi;交通 GIS 及應用課程論文- 11 - pathi = s; isUnions = true; ds = 0; /選擇最短路徑 int min, t; for(int i=1; in; +i) min = MAX; for(int j=0; jn; +j) /s 編號不一定就是 0，鄙視思維定勢 if(!isUnionj & dj min) min = dj; t = j; isUniont = true; /更新 t 相鄰點的值 for(int k=0