一種改進(jìn)的空間網(wǎng)絡(luò)最短路徑算法

一種改進(jìn)的空間網(wǎng)絡(luò)最短路徑算法

0基于最短路徑的地理網(wǎng)絡(luò)模型近年來，國(guó)際學(xué)術(shù)界加強(qiáng)了對(duì)gis理論中空間關(guān)系的研究，地理網(wǎng)絡(luò)分析也取得了很大進(jìn)展。網(wǎng)絡(luò)分析包括最短路徑分析、資源配置、等時(shí)性問題等等,但在進(jìn)行網(wǎng)絡(luò)分析時(shí),還要根據(jù)不同的網(wǎng)絡(luò),建立起相應(yīng)的網(wǎng)絡(luò)分析模型.這里,所謂網(wǎng)絡(luò)模型,是指將現(xiàn)實(shí)中的地理網(wǎng)絡(luò)實(shí)體,抽象化為網(wǎng)絡(luò)圖論理論中的網(wǎng)絡(luò)圖,并通過圖論中的網(wǎng)絡(luò)分析來實(shí)現(xiàn)地理網(wǎng)絡(luò)的最優(yōu)化問題.在網(wǎng)絡(luò)分析中,最短路徑問題的分析是最基本的,也是最關(guān)鍵的,如今,解決最短路徑分析問題的方法雖然已經(jīng)很成熟,例如以Dijkstra算法為代表的寬度優(yōu)先搜索方法、動(dòng)態(tài)規(guī)劃方法等等,但作為網(wǎng)絡(luò)分析的關(guān)鍵環(huán)節(jié),由于網(wǎng)絡(luò)分析的存儲(chǔ)量和計(jì)算量過于龐大,算法的效率將直接影響到整個(gè)系統(tǒng)的性能.因此對(duì)該算法效率的改進(jìn)歷來是人們研究的熱點(diǎn).本文針對(duì)上述問題,在最短路徑分析的經(jīng)典算法(即Dijkstra算法)的基礎(chǔ)上,對(duì)網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)和計(jì)算方法作了一系列的改進(jìn),改進(jìn)的Dijkstra算法較之Dijkstra算法,效率得到一定提高,系統(tǒng)的性能也有相應(yīng)的優(yōu)化,并實(shí)現(xiàn)了最短路徑的可視化計(jì)算.1網(wǎng)絡(luò)最優(yōu)路徑分析的實(shí)現(xiàn)方法1.1網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)的建立和存儲(chǔ)大家知道,空間網(wǎng)絡(luò)數(shù)據(jù)是網(wǎng)絡(luò)模型的基礎(chǔ),而由于空間網(wǎng)絡(luò)數(shù)據(jù)具有空間數(shù)據(jù)基本的屬性特征和空間特征,因而在GIS中,常將空間事物抽象成點(diǎn)、線、面等幾何要素,并在點(diǎn)、線之間建立拓?fù)潢P(guān)聯(lián)關(guān)系.例如,地理道路網(wǎng)絡(luò)空間特征中的交叉路口坐標(biāo)和道路位置坐標(biāo),是在地圖上借助圖形來識(shí)別和解釋的,而在計(jì)算機(jī)中,則按照拓?fù)浣Y(jié)構(gòu)加以定義;而其屬性特征有道路名稱、道路距離、交通流量等等.在實(shí)際工作中,盡管已擁有了空間數(shù)據(jù),關(guān)鍵還要建立起空間數(shù)據(jù)結(jié)構(gòu).地理網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)使用的是“弧段和結(jié)點(diǎn)”的數(shù)據(jù)結(jié)構(gòu),該數(shù)據(jù)結(jié)構(gòu)乃是建立在圖論的基礎(chǔ)上的,即將地理網(wǎng)絡(luò)表現(xiàn)為“由線串聯(lián)而成的點(diǎn)群”,如今,一般向量式GIS均采用這種數(shù)據(jù)結(jié)構(gòu).在此結(jié)構(gòu)下,結(jié)點(diǎn)可用來定義弧段之間的連接關(guān)系.在地理網(wǎng)絡(luò)中,由于大多數(shù)弧段與弧段之間的交點(diǎn)是具有拓?fù)湫缘慕稽c(diǎn),因而由此建立起來的地理網(wǎng)絡(luò)具有明顯的拓?fù)涮卣?另外,由于拓?fù)浣Y(jié)構(gòu)是明確定義空間結(jié)構(gòu)關(guān)系的一種數(shù)學(xué)方法,因此在GIS中,它不但用于空間數(shù)據(jù)的組織,而且在空間分析和應(yīng)用中都具有重要的意義.一般具有了拓?fù)浣Y(jié)構(gòu),就可以很快地確定一種地理實(shí)體相對(duì)于另一種地理實(shí)體的空間位置關(guān)系.由此可見,具有拓?fù)浣Y(jié)構(gòu)也是進(jìn)行網(wǎng)絡(luò)分析的必要條件.對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的存儲(chǔ),傳統(tǒng)的是采用圖論中的鄰接矩陣方法,其存儲(chǔ)量為N×N(N為網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)).通常的地理網(wǎng)絡(luò),盡管結(jié)點(diǎn)很多,但與結(jié)點(diǎn)相關(guān)聯(lián)的結(jié)點(diǎn)數(shù)目并不多,一般都為稀疏圖,這樣,該存儲(chǔ)方法將浪費(fèi)大量的空間,而且在計(jì)算時(shí)亦要花費(fèi)大量的時(shí)間遍歷無(wú)意義的數(shù)據(jù),故本文采用了鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),其存儲(chǔ)量為E(E為結(jié)點(diǎn)列表中,同結(jié)點(diǎn)關(guān)聯(lián)的所有弧段數(shù)目),一般用鄰接表表示圖比用鄰接矩陣法能節(jié)省大量的存儲(chǔ)空間,尤其是在表示與結(jié)點(diǎn)和邊相關(guān)信息較多的地理網(wǎng)絡(luò)時(shí).1.2基于最短路徑的搜索方法在最短路徑算法中,是利用了以下性質(zhì),即兩結(jié)點(diǎn)間的最短路徑包含了其內(nèi)部其它的最短路徑,而算法實(shí)現(xiàn)的主要技術(shù)是松弛技術(shù),而這種技術(shù)的實(shí)質(zhì)是反復(fù)減小每個(gè)結(jié)點(diǎn)實(shí)際路徑權(quán)值的上限,直到該上限等于最短路徑的權(quán)值為止.在圖論中,最短路徑的求法采用了同圖的寬度優(yōu)先搜索方法類似的思想,如Dijkstra就提出了按路徑長(zhǎng)度遞增的次序來產(chǎn)生最短路徑的算法.此算法(設(shè)網(wǎng)中權(quán)值均為非負(fù))首先是把網(wǎng)中的所有頂點(diǎn)分成兩個(gè)集合,即一個(gè)是將以StartPoint為源點(diǎn)的已經(jīng)確定了最短路徑的所有終點(diǎn)都并入S集合,S集合的初態(tài)應(yīng)只包含StartPoint;另一個(gè)集合T則是尚未確定最短路徑的頂點(diǎn)的集合,T集合的初態(tài)則包含除源點(diǎn)StartPoint外的網(wǎng)中所有頂點(diǎn),然后按各頂點(diǎn)與源點(diǎn)StartPoint間的最短路徑長(zhǎng)度遞增的次序,來設(shè)置優(yōu)先級(jí)隊(duì)列Q,再通過優(yōu)先級(jí)隊(duì)列Q的相應(yīng)操作,逐個(gè)把T集合中的頂點(diǎn)加入到S集合中去,并使得從StartPoint到S集合中各頂點(diǎn)的路徑長(zhǎng)度始終不大于從StartPoint到集合T中各頂點(diǎn)的路徑長(zhǎng)度.1.3shctorpothtee最短路徑計(jì)算這里要實(shí)現(xiàn)的最短路徑屬于單源最短路徑的問題.其實(shí)現(xiàn)過程如下:輸入:網(wǎng)絡(luò)中進(jìn)行路徑分析的兩個(gè)結(jié)點(diǎn)StartPoint,EndPoint;輸出:兩個(gè)結(jié)點(diǎn)StartPoint,EndPoint之間的最短路徑樹(ShortPathTree),即最短路徑;實(shí)現(xiàn)步驟為:(1)選擇要進(jìn)行計(jì)算的StartPoint和EndPoint兩個(gè)結(jié)點(diǎn);(2)對(duì)StartPoint和EndPoint兩個(gè)結(jié)點(diǎn)進(jìn)行連通分析,即采用寬度優(yōu)先搜索方法,來快速判斷這兩個(gè)結(jié)點(diǎn)之間是否連通,也就是確定是否存在計(jì)算最短路徑的必要.若連通,則進(jìn)行(3),否則,退出計(jì)算;(3)使用改進(jìn)的Dijkstra算法,計(jì)算StartPoint和EndPoint兩個(gè)結(jié)點(diǎn)之間的最短路徑(改進(jìn)的Dijkstra算法的計(jì)算過程將在下面具體介紹和討論);(4)經(jīng)過對(duì)計(jì)算出來的最短路徑樹進(jìn)行優(yōu)化處理之后,生成最終的最短路徑樹(ShortPathTree),輸出并退出.2基于dij推動(dòng)的多級(jí)陣列q的實(shí)現(xiàn)在Dijkstra算法的計(jì)算過程中,通過設(shè)置優(yōu)先級(jí)隊(duì)列Q的操作,將集合S中的結(jié)點(diǎn)加入到集合T中,一般的Dijkstra算法是采用線性數(shù)組來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列Q,而這里采用二叉堆這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列Q的一系列操作.2.1集合s的數(shù)據(jù)結(jié)構(gòu)Willioms在1964年提出了堆排序方法,該方法引入了堆這種特定的數(shù)據(jù)結(jié)構(gòu).這里二叉堆結(jié)構(gòu)可以被視為一棵完全二叉樹,而且其含義表明,完全二叉樹中所有非終端結(jié)點(diǎn)的值均不大于(或不小于)其左、右子結(jié)點(diǎn)的值.除了用于堆排序之外,二叉堆最常見的應(yīng)用是作為高效的優(yōu)先級(jí)隊(duì)列.該優(yōu)先級(jí)隊(duì)列是一種用來維護(hù)由一組元素構(gòu)成集合S的數(shù)據(jù)結(jié)構(gòu),而且這一組元素中的每一個(gè)都有一個(gè)關(guān)鍵字key.在分時(shí)計(jì)算機(jī)上,進(jìn)行作業(yè)調(diào)度和進(jìn)行事件驅(qū)動(dòng)的仿真器都要用到優(yōu)先級(jí)隊(duì)列,而且通常采用二叉堆結(jié)構(gòu)來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列.一般作用于優(yōu)先級(jí)隊(duì)列上的二叉堆的相應(yīng)操作有:Heapify(S):即首先將集合S調(diào)整成二叉堆,并設(shè)定其根結(jié)點(diǎn)具有最小關(guān)鍵字;然后該操作從堆的根結(jié)點(diǎn)開始,通過對(duì)當(dāng)前結(jié)點(diǎn)的左右子樹關(guān)鍵字的比較,來調(diào)整相應(yīng)結(jié)點(diǎn)在堆中的正確位置,即通常所謂的“篩選”過程,而且此操作為維持堆性質(zhì)的關(guān)鍵.Heap-Insert(x,S):S∪{x}←S,即將元素x插入集合S,并調(diào)用Heapify將其調(diào)整成二叉堆.該操作是首先將堆加以擴(kuò)展,即在樹的最后一層加一片葉子,然后遍歷由新加的結(jié)點(diǎn)葉子到根的路徑,以找到放新元素的合適位置.Heap-Extract-Min(S):即抽取具有最小關(guān)鍵字的元素,并調(diào)用Heapify將其調(diào)整成二叉堆.該操作可通過對(duì)堆的Heapify操作來實(shí)現(xiàn).其運(yùn)行時(shí)間主要花費(fèi)在調(diào)整成二叉堆的操作上.2.2改進(jìn)的實(shí)現(xiàn)方法dankflow算法對(duì)改進(jìn)的Dijkstra算法的實(shí)現(xiàn),采用了面向?qū)ο蟮姆椒?對(duì)網(wǎng)絡(luò)分析所用到的地理實(shí)體進(jìn)行面向?qū)ο蠓庋b,并實(shí)現(xiàn)最短路徑的可視化計(jì)算.2.2.1最短路徑計(jì)算面向?qū)ο蟮某绦蛟O(shè)計(jì)(OOP)是結(jié)構(gòu)化語(yǔ)言的自然延伸.由于OOP先進(jìn)的編程方法,會(huì)產(chǎn)生清晰而又容易擴(kuò)展及維護(hù)的程序,且一旦為程序建立了一個(gè)對(duì)象,就可以在其它的程序中使用這個(gè)對(duì)象,完全不必重新編制繁復(fù)的代碼,因而對(duì)象的重復(fù)使用可以大大地節(jié)省開發(fā)時(shí)間和切實(shí)地提高工作效率.一個(gè)對(duì)象有3個(gè)突出特征,即封裝性、繼承性、多態(tài)性.這里構(gòu)建了進(jìn)行最短路徑分析時(shí)所用到的地理對(duì)象類TGEONET、TNODELIST、TARCLIST、TNODE、TARC、SHORTPATHTREE.地理網(wǎng)絡(luò)類之間的繼承關(guān)系如圖1所示:圖中,TGEONET為進(jìn)行計(jì)算的地理網(wǎng)絡(luò)類,最短路徑的計(jì)算過程就在其中實(shí)現(xiàn);TNODELIST為地理網(wǎng)絡(luò)中的結(jié)點(diǎn)列表,它存儲(chǔ)了網(wǎng)絡(luò)結(jié)點(diǎn)TNODE的信息;TARCLIST為地理網(wǎng)絡(luò)中的弧段列表,它存儲(chǔ)了網(wǎng)絡(luò)弧段TARC的信息.其中,TNODE類封裝網(wǎng)絡(luò)中結(jié)點(diǎn)的信息,包括頂點(diǎn)的標(biāo)識(shí)ID、頂點(diǎn)的X、Y坐標(biāo)、同頂點(diǎn)連接的弧段列表ADJARCLIST,以及在求最短路徑時(shí)用到的用來存放當(dāng)前所求最短路徑點(diǎn)的列表CurPath;TARC類封裝弧段的信息包括弧段的標(biāo)識(shí)INDEX、弧段的長(zhǎng)度LENGTH、起始點(diǎn)NODEFROM、終結(jié)點(diǎn)NODETO、組成弧段的節(jié)點(diǎn)坐標(biāo)XYS及其節(jié)點(diǎn)數(shù)POINTCOUNT;SHORTPATHTREE為源點(diǎn)StartPoint至EndPoint之間的最短路徑樹,其中存儲(chǔ)的是最短路徑樹中的結(jié)點(diǎn)信息.2.2.2改進(jìn)的dijksta算法流程結(jié)構(gòu)的圖如圖所示2.2.3生成控制錯(cuò)誤(1)初始化操作首先搜索與源結(jié)點(diǎn)StartPoint關(guān)聯(lián)的結(jié)點(diǎn)Adj[StartPoint],然后初始化結(jié)點(diǎn)列表NodeList中所有結(jié)點(diǎn)的權(quán)值cost[Nodei],調(diào)用Heap-Insert方法實(shí)現(xiàn)初始化Initialize操作,來初始化優(yōu)先級(jí)隊(duì)列Heap,同時(shí)創(chuàng)建堆Heap中結(jié)點(diǎn)與結(jié)點(diǎn)列表NodeList中結(jié)點(diǎn)相互關(guān)聯(lián)的索引Index.(2)抽取最短距離結(jié)點(diǎn)操作即對(duì)優(yōu)先級(jí)隊(duì)列Heap的操作,通過調(diào)用Heap-Extract-Min,選擇結(jié)點(diǎn)Node[j],使得cost[j]=min{cost[I]∈Node[i]∈Nodelist}其中,Node[j]為當(dāng)前求得的從StartPoint出發(fā)的最短路徑終點(diǎn).(3)松弛操作對(duì)從Node[j]出發(fā)的結(jié)點(diǎn)Node[k]進(jìn)行松弛操作,松弛操作是通過Decrease-Key方法來實(shí)現(xiàn),即若cost[j]+cost[j,k]<cost[k],則修改cost[k]=cost[j]+cost[j,k];同時(shí),將結(jié)點(diǎn)Node[k]通過Heap-Insert加到優(yōu)先級(jí)隊(duì)列Heap中,并相應(yīng)更新索引表Index.而索引表中記錄的是結(jié)點(diǎn)列表NodeList與二叉堆中結(jié)點(diǎn)之間的相對(duì)位置索引.(4)重復(fù)步驟2、3,直至Node[j]=EndPoint.(5)結(jié)束.2.3oelist算法Dijkstra算法同寬度優(yōu)先搜索算法相似,要遍歷從每一結(jié)點(diǎn)出發(fā)的所有結(jié)點(diǎn),最終生成的不僅是起點(diǎn)到終點(diǎn)的最短路徑,而且還求出起點(diǎn)到網(wǎng)絡(luò)圖中其它所有結(jié)點(diǎn)的最短路徑,實(shí)際上生成的是其它結(jié)點(diǎn)到起點(diǎn)的最短路徑樹.由于傳統(tǒng)Dijkstra算法是使用線性數(shù)組結(jié)構(gòu),因此每次操作都要遍歷整個(gè)結(jié)點(diǎn)列表NodeList,即順序遍歷整個(gè)最短路徑樹,其整個(gè)算法的運(yùn)行時(shí)間僅為O(N2);而使用二叉堆結(jié)構(gòu)的改進(jìn)Dijkstra算法則僅僅遍歷二叉堆,即僅遍歷最短路徑樹中從根結(jié)點(diǎn)到當(dāng)前進(jìn)行操作的結(jié)點(diǎn),即遍歷次數(shù)僅僅是二叉堆Heap的高度lg(N),故算法的執(zhí)行效率大為提高,整個(gè)算法的運(yùn)行時(shí)間為O(ElgN).表1中列出了線性數(shù)組與二叉堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的各種操作的最壞情況緊湊時(shí)間界.從該表中可見,采用二叉堆來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列要比使用線性數(shù)組節(jié)省時(shí)間.雖然采用二叉堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列較之使用線性數(shù)組結(jié)構(gòu)要優(yōu)秀得多,但在對(duì)結(jié)點(diǎn)進(jìn)行松弛操作的時(shí)候,要用到二叉堆的查找Search操作,然而二叉堆不能有效地支持查找操作.針對(duì)這一點(diǎn),本文創(chuàng)建了二叉堆Heap中的結(jié)點(diǎn)位置與結(jié)點(diǎn)列表Nodelist中結(jié)點(diǎn)位置之間的索引Index,通過索引表Index,能夠快速地對(duì)二叉堆中的結(jié)點(diǎn)在Nodelist中的位置進(jìn)行定位,這就大大減少了對(duì)結(jié)點(diǎn)進(jìn)行定位時(shí)所花費(fèi)的時(shí)間,同時(shí)也進(jìn)一步優(yōu)化了算法.3基于改進(jìn)的dij不斷優(yōu)化的最短路徑計(jì)算本文在進(jìn)行案例分析時(shí)所選用的開發(fā)平臺(tái)為Delphi4.0、Windows98,并采用控件化編程的思想,首先將最短路徑分析過程封裝到非可視化控件GeoNet中,然后同其它GIS功能控件,如MapViewer,GeoView等連接,快速組裝成最短路徑分析系統(tǒng)(見圖3).本文實(shí)驗(yàn)所采用的數(shù)據(jù)是美國(guó)某一地區(qū)的道路網(wǎng)絡(luò)數(shù)據(jù),文件中一共有4788條地理實(shí)體記錄,經(jīng)初始化,對(duì)所有記錄構(gòu)建網(wǎng)絡(luò)所用時(shí)間為10s左右,網(wǎng)絡(luò)共有2964個(gè)結(jié)點(diǎn),而在計(jì)算最短路徑時(shí),使用改進(jìn)的Dijkstra算法所花費(fèi)的時(shí)間通常只有幾秒鐘,而