GIS網(wǎng)絡(luò)分析功能的實(shí)現(xiàn)摘要:網(wǎng)絡(luò)分析作為的重要功能,在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計(jì)中發(fā)揮了重要的作用。隨著系統(tǒng)集成應(yīng)用的不斷深入,為了滿足用戶的應(yīng)用需求,我們通過(guò)二次開發(fā)的手段,為一些平臺(tái)定制了網(wǎng)絡(luò)分析功能。利用經(jīng)典的Dijkstra算法,結(jié)合數(shù)據(jù)和平臺(tái)特點(diǎn),通過(guò)簡(jiǎn)單的程序設(shè)計(jì)可以實(shí)現(xiàn)復(fù)雜的網(wǎng)絡(luò)分析功能。 關(guān)鍵詞:網(wǎng)絡(luò)分析;Dijkstra算法;網(wǎng)絡(luò)拓?fù)潢P(guān)系 網(wǎng)絡(luò)分析作為GIS應(yīng)用最主要的功能之一,在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計(jì)中發(fā)揮了重要的作用。隨著計(jì)算機(jī)及測(cè)繪技術(shù)的不斷發(fā)展,地理信息產(chǎn)業(yè)得以蓬勃發(fā)展,近幾年來(lái)我中心面向社會(huì)的GIS應(yīng)用開發(fā)不斷增多,逐漸形成以MapObject和 MapGuide為主流的GIS應(yīng)用開發(fā)體系。MapGuide是Autodesk公司的商業(yè)webgis產(chǎn)品,該產(chǎn)品合理的分配了客戶機(jī)和服務(wù)器的運(yùn)算,實(shí)現(xiàn)了矢量數(shù)據(jù)的直接訪問(wèn),優(yōu)良的性能、可擴(kuò)展性強(qiáng),是webgis應(yīng)用的首選產(chǎn)品之一。MapObject是美國(guó)ESRI生產(chǎn)的控件式GIS系統(tǒng),它性能穩(wěn)定,價(jià)格適中,是目前非常流行的GIS系統(tǒng)開發(fā)平臺(tái)。但這兩個(gè)系統(tǒng)都沒(méi)有現(xiàn)成的網(wǎng)絡(luò)分析功能,為了滿足用戶的應(yīng)用需求,我們通過(guò)二次開發(fā)為MapGuide和MapObject分別定制了網(wǎng)絡(luò)分析功能。 網(wǎng)絡(luò)分析中最基本最關(guān)鍵的問(wèn)題是最短路徑問(wèn)題。最短路徑不僅僅指一般地理意義上的距離最短,還可以引申到其他的度量,如時(shí)間、費(fèi)用、線路容量等。相應(yīng)地,最短路徑問(wèn)題就成為最快路徑問(wèn)題、最低費(fèi)用問(wèn)題等。其實(shí),無(wú)論是距離最短、時(shí)間最快還是費(fèi)用最低,它們的核心算法都是最短路徑算法。 最短路徑的求解,必須把現(xiàn)實(shí)生活中的道路、管線等各種網(wǎng)絡(luò)抽象成一種數(shù)學(xué)結(jié)構(gòu),這種抽象出來(lái)的數(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)的建立和高效能最短路徑算法。下面我們就這兩個(gè)問(wèn)題進(jìn)行深入探討。 1最短路徑算法 最短路徑算法,關(guān)鍵是將一個(gè)物理網(wǎng)絡(luò)結(jié)構(gòu)抽象為一個(gè)數(shù)學(xué)網(wǎng)絡(luò)結(jié)構(gòu),再利用數(shù)學(xué)方法進(jìn)行求解。 1.1算法選擇 在數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域網(wǎng)絡(luò)被抽象為圖,再利用圖論的方法計(jì)算最短路徑。目前提出的基于圖論的最短路徑的算法大約有17種。經(jīng)專家測(cè)試,其中有3種效果比較好,它們分別是:TQQ、DKA以及DKD。其中TQQ算法的基礎(chǔ)是圖增長(zhǎng)理論;后兩種算法則是基于Dijkstra的算法。Dijkstra算法是經(jīng)典的最短路徑算法,目前多數(shù)系統(tǒng)解決最短路徑問(wèn)題采用了Dijkstra算法為理論基礎(chǔ),只是不同系統(tǒng)對(duì)Dijkstra算法采用了不同的實(shí)現(xiàn)方法。 1.2經(jīng)典Dijkstra算法的主要思想Dijkstra算法的基本思路是:將頂點(diǎn)分成兩個(gè)集合S和T,已求出最短路的點(diǎn)置于S中,其它點(diǎn)置于T中。開始時(shí)S中僅含起點(diǎn)vs,其它點(diǎn)全在T中,隨著求最短路迭代工作的進(jìn)行,S中的點(diǎn)逐漸增多,當(dāng)終點(diǎn)vt也被納入S中時(shí),迭代結(jié)束。為了便于計(jì)算和區(qū)分各頂點(diǎn)是否已進(jìn)入集合S,給已求出到起點(diǎn)最短路的點(diǎn)vk賦以標(biāo)號(hào)。這個(gè)標(biāo)號(hào)由兩部分組成,記為(d(vs,vk),i)其中i為vk到起點(diǎn)最短路上的前點(diǎn),d(vs,vk為從起點(diǎn)vs到vk的最短路長(zhǎng)。因每個(gè)標(biāo)號(hào)含有兩部分,故稱為雙標(biāo)號(hào)法。最短路徑算法的基本過(guò)程如下:(1)給始點(diǎn)vs賦以標(biāo)號(hào)(0,s),并置vs于置,其它頂點(diǎn)于集合T中。 (2)對(duì)圖G里起點(diǎn)在S中終點(diǎn)在T中的邊ei,計(jì)算: d(vs,vk)=mimd(vs,vi)+minjWijvis,vjT并將vk置于S中,同時(shí)賦給它標(biāo)號(hào)(d(vsvk),i)。 (3)重復(fù)步驟(2),當(dāng)vtS時(shí)計(jì)算結(jié)束vt的第一個(gè)標(biāo)號(hào)給出vsvt的最短路長(zhǎng);利用第 二個(gè)標(biāo)號(hào)反向追蹤,可得最短路徑。 2網(wǎng)絡(luò)拓?fù)潢P(guān)系的獲取與高效訪問(wèn) 要想用計(jì)算機(jī)程序?qū)崿F(xiàn)Dijkstra算法,關(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)行高效能訪問(wèn)。 2.1拓?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數(shù)據(jù)通常是圖形數(shù)據(jù)和屬性數(shù)據(jù)的有機(jī)集合。在ARC/INFO下利用命令CLEAN對(duì)道路網(wǎng)數(shù)據(jù)構(gòu)建網(wǎng)絡(luò)拓?fù)?我們可以看到屬 性表,其屬性數(shù)據(jù)中包括_Fnode(起點(diǎn))和_Tnode(終點(diǎn))兩個(gè)屬性項(xiàng)。該屬性表中包含了一個(gè)完備的網(wǎng)絡(luò)拓?fù)潢P(guān)系,即記錄了該圖擁有多少個(gè)節(jié)點(diǎn),又記錄了節(jié)點(diǎn)與節(jié)點(diǎn)的連通關(guān)系,不同的_Fnode、_Tnode標(biāo)號(hào)代表不同的節(jié)點(diǎn),及一條線的起始節(jié)點(diǎn)和終止節(jié)點(diǎn),擁有相同節(jié)點(diǎn)的線相連,從該表大家應(yīng)該很清楚的看出道路網(wǎng)的拓?fù)浣Y(jié)構(gòu)。構(gòu)建網(wǎng)絡(luò)拓?fù)涫且粋€(gè)復(fù)雜的過(guò)程,在搭建用戶應(yīng)用系統(tǒng)時(shí),一般使用ARC/INFO等專業(yè)軟件事先構(gòu)件好網(wǎng)絡(luò)拓?fù)潢P(guān)系,使用時(shí)只需訪問(wèn)GIS數(shù)據(jù)的屬性表即可。 2.2網(wǎng)絡(luò)拓?fù)潢P(guān)系的高效訪問(wèn) 利用上面的屬性表我們可以有效的解讀出一個(gè)網(wǎng)絡(luò)拓?fù)潢P(guān)系,在按標(biāo)記法實(shí)現(xiàn)Dijkstra算法的過(guò)程中,核心步驟就是從未標(biāo)記的點(diǎn)中選擇一個(gè)權(quán)值最小的弧段,即上面所述算法的2)3)步。這是一個(gè)循環(huán)比較的過(guò)程,如果不采用任何技巧,要選擇一個(gè)權(quán)值最小的弧段就必須對(duì)屬性表進(jìn)行多次掃描,在大數(shù)據(jù)量的情況下,這無(wú)疑是一個(gè)制約計(jì)算速度的瓶頸。下面主要就如何從含拓?fù)潢P(guān)系的屬性表中解析一個(gè)簡(jiǎn)潔高效的網(wǎng)絡(luò)拓?fù)浯鎯?chǔ)結(jié)構(gòu)進(jìn)行討論。在數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域中網(wǎng)絡(luò)拓?fù)浔怀橄鬄閳D,所以其基礎(chǔ)是圖的存儲(chǔ)表示。一般而言,無(wú)向圖可以用鄰接矩陣和鄰接多重表來(lái)表示,而有向圖則可以用鄰接表和十字鏈表表示,其優(yōu)缺點(diǎn)的比較見(jiàn)表2。 綜合以上4種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn),我們采用了兩個(gè)數(shù)組來(lái)存儲(chǔ)網(wǎng)絡(luò)圖,一個(gè)用來(lái)存儲(chǔ)和弧段相關(guān)的數(shù)據(jù)(Net-ArcList),另一個(gè)則存儲(chǔ)和頂點(diǎn)相關(guān)的數(shù)據(jù)(Net-NodeIndex)。Net-ArcList用一個(gè)數(shù)組維護(hù)并且以弧段起點(diǎn)的點(diǎn)號(hào)來(lái)順序排列,同一起點(diǎn)的弧段按權(quán)值排序。這個(gè)數(shù)組類似于鄰接矩陣的壓縮存儲(chǔ)方式,其內(nèi)容則具有鄰接多重表的特點(diǎn),即一條邊以兩頂點(diǎn)表示。Net-NodeIndex則相當(dāng)于一個(gè)記錄了頂點(diǎn)出度的索引表,通過(guò)它可以很容易地得到此頂點(diǎn)的出度和與它相連的第一條弧段在弧段數(shù)組中的位置。這樣就可以以最快速度搜索出與任意節(jié)點(diǎn)相連的邊在頂點(diǎn)已編號(hào)的情況下,建立Net-ArcList和Net-NodeIndex兩個(gè)表以及對(duì)Net-ArcList的排序其時(shí)間復(fù)雜度共為O(2n+lgn),否則為O(m+2n+lgn)。這個(gè)結(jié)構(gòu)所需的空間也是必要條件下最小的,記錄了m個(gè)頂點(diǎn)以及n條邊的相關(guān)信息,與鄰接多重表是相同的。利用表1所提供的屬性表,有向圖只需對(duì)Fode進(jìn)行一次排序和一次索引,即可得到上面的兩個(gè)數(shù)組,對(duì)與無(wú)向圖則稍復(fù)雜一點(diǎn)。最后我們所要作的事情就是進(jìn)行算法2)3)步的循環(huán)求解最短路徑。我們利用該方法在Vb開發(fā)環(huán)境中針對(duì)MapObject定制了具有網(wǎng)絡(luò)分析功能的動(dòng)態(tài)連接庫(kù);在ASP.Net開發(fā)環(huán)境下,利用ASP.NetWeb服務(wù)為MapGuide成功 的定制了網(wǎng)絡(luò)路徑分析服務(wù)器。在算法的具體實(shí)現(xiàn)中我們還吸收了Moore-Pape算法的優(yōu)點(diǎn),使運(yùn)算速度有了進(jìn)一步提高,經(jīng)測(cè)試,2萬(wàn)個(gè)節(jié)點(diǎn),25000條路全部遍歷,平均只需1秒。完全可以滿足用戶在速度方面的需求。