淺談GIS中網(wǎng)絡(luò)分析與最短路徑的實(shí)現(xiàn)

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

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

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

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

5、 及應(yīng)用課程論文- 2 -2. 網(wǎng)絡(luò)拓?fù)潢P(guān)系的建立網(wǎng)絡(luò)拓?fù)潢P(guān)系的建立網(wǎng)絡(luò)分析是空間分析的一個(gè)重要方面，是依據(jù)網(wǎng)絡(luò)拓?fù)潢P(guān)系（線性實(shí)體之間、線性實(shí)體與結(jié)點(diǎn)之間、結(jié)點(diǎn)與結(jié)點(diǎn)之間的連結(jié)、聯(lián)通關(guān)系） ，并通過考察網(wǎng)絡(luò)元素的空間、屬性數(shù)據(jù)，對(duì)網(wǎng)絡(luò)的性能特征進(jìn)行多方面的分析計(jì)算。對(duì)地理網(wǎng)絡(luò)、城市基礎(chǔ)設(shè)施】【2網(wǎng)絡(luò)進(jìn)行地理分析和模型化的關(guān)鍵技術(shù)是用什么樣的方式抽象出網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),及節(jié)點(diǎn)與節(jié)點(diǎn)的連通關(guān)系,并對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行高效能訪問。2.1 網(wǎng)絡(luò)數(shù)據(jù)模型的基本概念網(wǎng)絡(luò)數(shù)據(jù)模型的基本概念網(wǎng)絡(luò)是由若干線性實(shí)體互連而成的一個(gè)系統(tǒng)，資源由網(wǎng)絡(luò)來傳輸，實(shí)體間的聯(lián)絡(luò)也由網(wǎng)絡(luò)來達(dá)成。網(wǎng)絡(luò)數(shù)據(jù)模型是真實(shí)世界中網(wǎng)絡(luò)系統(tǒng)（如交通

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

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

8、。同時(shí)，量多變形之所以相鄰是因?yàn)槎呔哂泄餐倪吔?。交?GIS 及應(yīng)用課程論文- 3 -為了能夠更好的描述路網(wǎng)拓?fù)浣Y(jié)構(gòu)的建立過程，首先介紹一下描述路網(wǎng)的基本要素及各要素的屬性。描述路網(wǎng)的基本要素：點(diǎn)對(duì)象：路網(wǎng)中道路和道路的交叉點(diǎn)以及道路的端點(diǎn)。先對(duì)象：用弧或鏈表示路段，形成路段的基本規(guī)則是：道路的所有車道合在一起，兩結(jié)點(diǎn)之間的部分形成一個(gè)路段。面對(duì)像：有路段線圍成的封閉區(qū)域。相關(guān)路網(wǎng)要素的屬性：路段標(biāo)識(shí)符（用編號(hào)表示） 起、終點(diǎn)標(biāo)識(shí)符（用編號(hào)表示）路段名稱路段長度道路類別結(jié)點(diǎn)表示符號(hào)結(jié)點(diǎn)坐標(biāo)通常，可以用賦權(quán)圖來表示路網(wǎng)。具體做法是分別存儲(chǔ)點(diǎn)狀實(shí)體 結(jié)點(diǎn)，線狀實(shí)體兩點(diǎn)間的路段，結(jié)點(diǎn)和路段的屬性

9、信息，以及實(shí)體間的拓?fù)潢P(guān)系（主要是連通性和方向性） 。這樣從圖論的角度看，便將路網(wǎng)轉(zhuǎn)化為一個(gè)圖。進(jìn)一步還可以在每一條邊上定義權(quán)，這樣便得到了一個(gè)賦權(quán)圖。從而，確定某兩地間的最優(yōu)路線問題便可以轉(zhuǎn)化為在賦權(quán)圖上求兩點(diǎn)間的最短路徑問題。對(duì)于矢量圖形的拓?fù)潢P(guān)系的描述，主要有基于網(wǎng)路的拓?fù)淠Ｐ秃突邳c(diǎn)集拓?fù)淅碚摰耐負(fù)淠Ｐ汀；诰W(wǎng)絡(luò)的拓?fù)淠Ｐ途哂兄庇^、結(jié)構(gòu)清晰、互換性強(qiáng)、便于組織存】【4儲(chǔ)等優(yōu)點(diǎn)。路網(wǎng)拓?fù)潢P(guān)系主要討論線與線之間的聯(lián)通性關(guān)系，即將其按結(jié)點(diǎn)和邊的關(guān)系抽象為圖的結(jié)構(gòu)，這在 GIS 中稱為構(gòu)建網(wǎng)絡(luò)的拓?fù)潢P(guān)系，在計(jì)算機(jī)中這種拓?fù)潢P(guān)系與面無關(guān)，拓?fù)潢P(guān)系中只記錄了線與結(jié)點(diǎn)的關(guān)系，而沒有線與面的關(guān)系，所以

10、不是完備的拓?fù)潢P(guān)系。路網(wǎng)拓?fù)浣Y(jié)構(gòu)主要包括兩種對(duì)象，結(jié)點(diǎn)（Node）對(duì)象和邊（Link）對(duì)象。結(jié)點(diǎn)對(duì)象主要包括結(jié)點(diǎn)序號(hào)，結(jié)點(diǎn)屬性和它附近的相關(guān)信息，及與之相連接的編序號(hào)；邊對(duì)象應(yīng)包括編序號(hào)，長度信息，兩個(gè)端點(diǎn)序號(hào)。根據(jù)結(jié)點(diǎn)對(duì)象相連接的邊序號(hào)和邊對(duì)象的兩個(gè)端點(diǎn)序號(hào)，就建立了結(jié)點(diǎn)之間的連接特性。路網(wǎng)的拓?fù)浣Y(jié)構(gòu)的生成主要找出各路段之間的直接連通性，實(shí)現(xiàn)算法是找出相應(yīng)圖層中的所有線圖元，然后判斷任意兩線圖元是否相交，根據(jù)交點(diǎn)和頂點(diǎn)得到結(jié)點(diǎn)，根據(jù)橡膠關(guān)系判斷兩條邊是否直接相連接，再根據(jù)相關(guān)信息對(duì)相應(yīng)邊賦權(quán)值，利用拓?fù)涞玫降膸?quán)圖來查詢最短路徑。拓?fù)浣Y(jié)構(gòu)的建立過程表示為圖 2.1 的流程圖。交通 GIS 及

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

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

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

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

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

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

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

18、為 true 當(dāng)且僅當(dāng) v 屬于 s，即已經(jīng)求得從 v0 到 v 的最短路徑 for(v=0；v G.vexnum；v+) finalv=false；Dv=G.arcsv0v；for(w=0；w G.vexnum；w+) Pvw=false； /設(shè)置空路徑 if(Dv infinity) Pvv0=true；Pvv=true； Dv0=0;finalv0=true；/開始主循環(huán)，每次求得 v0 到某個(gè) v 定點(diǎn)的最短路徑，并且加 v 入到 s 集 for(i=1；i G.vexnum；i+) min=infinity； /infinity 是無窮的大數(shù) 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+) /更新當(dāng)前最短路徑和距離if(!finalw & (min+G.arcsvw) Dw) Dw=min+G.arcsvw；Pw=Pv;； Pww=true； 交通 GIS 及應(yīng)用課程論文- 8 - 交通 GIS 及應(yīng)用課程論文- 9 -參考文獻(xiàn)參考文獻(xiàn)1胡明光、張亮：GIS 網(wǎng)絡(luò)分析功能的實(shí)現(xiàn)J, 科教文匯2007 年9 月下旬刊。2Michael N.DeMers.武法東、付宗棠等譯: 地理信息系統(tǒng)基本原理M,電子工業(yè)出版社，2001 年第二版

20、，第 45-47 頁。3張榮梅：智能交通地理信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)J, 計(jì)算機(jī)應(yīng)用研究2000 年第一期，第 97-98 頁。4王行風(fēng)、賈凌：GIS 支持下的城市交通網(wǎng)絡(luò)最短路徑研究J ， 計(jì)算機(jī)與現(xiàn)代化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 及應(yīng)用課程論文- 10 -附附 錄錄下面是一個(gè)有關(guān)用鄰接矩陣實(shí)現(xiàn)的一

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

22、i = MAX; pathi = -1; isUnioni = false; /初始化出發(fā)點(diǎn)相鄰接的頂點(diǎn)距離 for(int i =0; in; +i) if(psi != MAX) di = psi;交通 GIS 及應(yīng)用課程論文- 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 編號(hào)不一定就是 0，鄙視思維定勢 if(!isUnionj & dj min) min = dj; t = j; isUniont = true; /更新 t 相鄰點(diǎn)的值 for(int k=0