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

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

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