改進的Dijkstra算法

1、湖北文理學院畢 業(yè) 論 文 （設 計）論文（設計）題目： Dijkstra算法在嵌入式GIS中的改進與研究 學 院 繼續(xù)教育學院 專 業(yè) 計算機應用技術 層 次 專 科 學 生 周金濤 指導教師 2016年5月20日- II -Dijkstra算法在嵌入式GIS中的改進與研究專業(yè)：計算機應用技術 學號：201421255 姓名：周金濤 指導教師：摘要：Dijkstra算法是求解嵌入式GIS系統(tǒng)中最短路徑的經(jīng)典算法，通過對Dijkstra算法進行分析，改變圖的存儲結(jié)構(gòu)和搜索方法，采用基于矩形限制區(qū)域的二叉排序樹改進算法，減少了內(nèi)存存儲空間，縮短了查詢時間，在一定程度上優(yōu)化了最短路徑的計算過程，實

2、際數(shù)據(jù)測試也表明了該算法的有效性。關鍵詞：Dijkstra算法；嵌入式GIS；最短路徑；矩形限制區(qū)域；二叉排序樹Research and Improvement of Dijkstra Algorithm to Embedded GIS SystemAbstract: Dijkstra algorithm is a classic algorithm to solve the shortest path in the embedded GIS system. Changing the storage structure of the graphics and the search method

3、, Dijkstra algorithm is modified by using binary sort tree based on rectangle boundary area through analyzing algorithm. The memory space needed is decreased and the search time is shortened and the algorithm has optimized calculation process in some degree. The algorithm is achieved good results by

4、 testing some data. Key Words: Dijkstra algorithm; embedded GIS; shortest path; rectangle boundary area; binary sort tree目 錄一、引言1二、Dijkstra算法及其存在的問題1三、基于Dijkstra算法的GIS路徑優(yōu)化2（一）改進的方面2（二）網(wǎng)絡路徑優(yōu)化的拓撲結(jié)構(gòu)3（三）限制搜索區(qū)域加載部分網(wǎng)絡模型4（四）Dijkstra算法的優(yōu)化改進5四、算法分析及測試7五、總結(jié)8參考文獻9一、引言隨著無線網(wǎng)絡的普及和智能移動設備的發(fā)展，嵌入式移動終端成為空間信息服務的核心組成和數(shù)字

5、城市的重要服務方式。最短路徑分析是GIS中最主要的一個基本功能，其中Dijkstra算法1由于算法穩(wěn)定，適應網(wǎng)絡拓撲，成為最短路徑規(guī)劃中的一個經(jīng)典算法。但由于Dijkstra算法是一種以起點為中心，想外層層搜索的盲目搜索算法，隨著網(wǎng)絡規(guī)模的擴大，對于嵌入式GIS無論是計算時間還是存儲空間上的需求都是十分巨大的，必須進行優(yōu)化。許多基于Dijkstra的最短路徑分析算法對此進行了改進。TQQ算法、DKA算法、DKD算法2以及最大相關邊法3、最大鄰接點法4減少了算法對存儲空間的需求，基于二叉堆優(yōu)先級隊列算法、四叉堆優(yōu)先級隊列的算法5以及排序優(yōu)化算法6則提高了算法的運行效率。這些算法或是節(jié)省了存儲空間

6、但導致系統(tǒng)的響應速度變慢，或是搜索時間變短但占用大量的存儲資源，無法在嵌入式GIS系統(tǒng)中正常運行。直線優(yōu)化Dijkstra算法7和快速Dijkstra優(yōu)化算法8對算法本身和存儲結(jié)構(gòu)都進行了優(yōu)化，但前者不太適合城市間道路的交通復雜情況，而且搜索過程中需要進行大量空間距離計算，而后者使用的村樹結(jié)構(gòu)十字鏈表過于復雜。因此，筆者試圖對Dijkstra算法進行數(shù)據(jù)結(jié)構(gòu)和運算方法的優(yōu)化處理，并將其應用于GIS路徑分析，希望能夠同時提高時間與空間效率。二、Dijkstra算法及其存在的問題經(jīng)典Dijkstra算法將網(wǎng)絡節(jié)點分成3部分：未標記結(jié)點、臨時標記結(jié)點和永久標記結(jié)點。網(wǎng)絡中所有結(jié)點首先初始化為未標記結(jié)

7、點，在搜索過程中與最短路徑中的結(jié)點相連通的結(jié)點為臨時標記結(jié)點，每次循環(huán)都是從臨時標記結(jié)點中搜索距源點路徑長度最短的結(jié)點作為永久標記結(jié)點，直至找到目標結(jié)點或者所有結(jié)點都成為永久標記結(jié)點，算法結(jié)束。設G=(V, E)是一個賦權有向圖，對于圖中的每一條邊都有權值w。單源的最短路徑問題是指求一源結(jié)點到其他所有結(jié)點的最短路徑及路徑長度。算法中把V分成兩個子集S和T，S集合用來存放已經(jīng)得到的最短路徑的結(jié)點，集合T滿足T=VS，用來存放目前還沒有參與計算的結(jié)點。設長度為N的一位數(shù)組DistN，用來存放從源點到圖中其他結(jié)點的最短路徑長度。設二維數(shù)組path_matrix，該矩陣用來記錄源點到圖中其他每個結(jié)點的

8、最短路徑所經(jīng)過的結(jié)點的集合，可以根據(jù)該矩陣進行路徑回溯。Dijkstra算法的流程如下：（1） 初始化集合S和集合T；（2） 利用圖的鄰接矩陣來初始化DistN數(shù)組；（3） 初始化path_matrix，使其中元素都為無窮大；（4） 從DistN中選擇最小的元素，假設此最小元素對應結(jié)點的索引為i，即結(jié)點i；（5） 將結(jié)點i加入到集合S中，同時從集合T中刪除結(jié)點i；（6） 根據(jù)結(jié)點i來更新距離數(shù)組DistN，只更新源點到集合T中的結(jié)點之間的距離，更新過程如下：if( Distj > Disti + path_matrixij )Distj = Disti + path_matrixij;（

9、7） 如果集合T不為空，則返回（3）；如果集合T為空，則結(jié)束算法。Dijkstra算法簡單直觀，容易編碼實現(xiàn)，已經(jīng)證明能夠計算出最短路徑的最優(yōu)解，有非常強的魯棒性，但它的計算效率是一個很大的問題。首先它采用帶權的鄰接矩陣存儲圖形數(shù)據(jù)，占用大量存儲空間；而且它是一種盲目搜索算法，對于具有n個結(jié)點的圖，計算源點到圖中所有其余結(jié)點的最短路徑的算法時間復雜度為O(n2)，對于一座大中型城市，無論是計算時間還是存儲空間上的開銷都是十分巨大的。算法的搜索速度受圖的存儲結(jié)構(gòu)的影響：搜索速度快，則圖的存儲空間就??；反之，圖的存儲空間大，則會降低搜索速度。所以經(jīng)典的Dijkstra算法不適合CPU處理能力較低、

10、存儲空間較小的嵌入式GIS，必須對其進行優(yōu)化。三、基于Dijkstra算法的GIS路徑優(yōu)化（一）改進的方面本文在改進時間與空間效率方面進行了以下重要改進：（1） 采用了一種新型的網(wǎng)絡存儲模型；（2） 采用矩形限制區(qū)域，結(jié)合方向優(yōu)化，分塊加載地圖數(shù)據(jù)，限制搜索區(qū)域；（3） 采用二叉排序樹優(yōu)化搜索臨時結(jié)點。（二）網(wǎng)絡路徑優(yōu)化的拓撲結(jié)構(gòu)傳統(tǒng)的Dijkstra算法在存儲圖形數(shù)據(jù)和運算時，采用n×n的鄰接矩陣，其中n為網(wǎng)絡模型的結(jié)點數(shù)。但是當網(wǎng)絡模型的節(jié)點數(shù)較大時，將占用大量的計算機內(nèi)存。而且在網(wǎng)絡的節(jié)點數(shù)很大而各結(jié)點的鄰接結(jié)點數(shù)又不多的情況下，有大量的無效的0元素或元素，造成了空間的浪費。在

11、此基礎上進行矩陣運算，必將浪費大量運行時間。為了避免空間的浪費，本文的優(yōu)化Dijkstra算法擬采用鄰接結(jié)點的結(jié)構(gòu)。該結(jié)構(gòu)通過構(gòu)造鄰接矩陣和判斷矩陣以實現(xiàn)拓撲數(shù)據(jù)的存儲。鄰接矩陣用來存儲結(jié)點之間的鄰接關系，判斷矩陣用來存儲鄰接矩陣中對應弧的權值。這樣只需要2×n×m的存儲空間，m為最大鄰接結(jié)點數(shù)，城市道路的相鄰一般不超過5個，所以占用空間為2×n×5。（1） 構(gòu)造鄰接矩陣。以結(jié)點為行，鄰接的結(jié)點為列，矩陣的行數(shù)為網(wǎng)絡模型的實際結(jié)點數(shù)，列數(shù)為網(wǎng)絡模型的最大相鄰結(jié)點數(shù)。鄰接矩陣的行按結(jié)點的索引號從小到大順序排列，與結(jié)點i鄰接的結(jié)點號寫在矩陣的第i行，如果結(jié)點

12、i的鄰接結(jié)點數(shù)小于最大鄰接結(jié)點數(shù)，則用0填充，直至填滿矩陣；（2） 構(gòu)造判斷矩陣。對照鄰接矩陣，用鄰接矩陣里的各個元素的鄰接關系對應的弧的權值填在矩陣的同一個位置上，就得到了相應的判斷矩陣；針對圖1所示的網(wǎng)絡模型，鄰接矩陣和判斷矩陣如圖2所示。這種存儲結(jié)構(gòu)既節(jié)省了存儲空間，也提高了運算速度。圖1 網(wǎng)絡模型實例 （a）鄰接矩陣 （b）判斷矩陣 圖2 鄰接矩陣和判斷矩陣實例（三）限制搜索區(qū)域加載部分網(wǎng)絡模型對于嵌入式系統(tǒng)，考慮硬件計算環(huán)境的限制，不需要一次性加載所有的網(wǎng)絡模型信息。本文采用的矩陣限制區(qū)域地圖數(shù)據(jù)選擇法9，以用戶輸入的起點和重點為地圖數(shù)據(jù)選擇的參考點，在參考點的基礎上，按照一定的規(guī)則

13、擴大范圍以生成最初的矩形區(qū)域。GIS兩點之間除空間距離關系之外，還有方向的關系，理想狀態(tài)下，兩點之間線段最短，這條線段作為一條道路存在的可能性極小，但這條從起點至終點的線段代表了一個路線的趨勢方向，順著這個趨勢方向的某條路徑是起點到終點的最短路徑的組成部分的可能性極大。因此在實際搜索過程中，可以借助備選結(jié)點到目標點的趨勢方向來確定最佳。在矩形限制區(qū)域內(nèi)遍歷道路圖層，求最短路徑的道路的范圍選擇原則如下：（1） 載入用戶設置的起點、終點、途經(jīng)點、障礙點，以起點和終點作為矩形區(qū)域?qū)蔷€上的兩個頂點，確定范圍，加載范圍以內(nèi)的數(shù)據(jù)，可以減少空間分析時所要檢索的臨時結(jié)點的數(shù)量；（2） 以A為起點，B為終點

14、。設Pi為與A點的鄰接點，求線段PjA與線段AB的夾角。如果夾角小于90°，把Pi選入范圍；否則繼續(xù)計算下一個A點的鄰接點Pi+1；（3） 以B為起點，A為終點。設Qj為B點的鄰接點，求線段QjB與線段AB的夾角。如果夾角小于90°，則把Qj選入范圍；否則繼續(xù)計算下一個B點的鄰接點Qj+1；（4） 以所有選入范圍的A點的鄰接點P為起點，B為終點，進行類似（2）中的計算；同時以所有選入范圍的B點的鄰接點Q為起點，A為終點，進行類似（3）中的計算；（5） 對（4）中計算完成之后，再進行更深一層的計算，直到兩個集合相交，就確定了算法所涉及的道路的范圍子集；（6） 在道路范圍自己中

15、應用Dijkstra算法，來求A點到所有其他結(jié)點的距離，到前點為B時，算法結(jié)束，并根據(jù)path_matrix矩陣回溯路徑，輸出路徑和最短距離；（7） 如果在限制范圍內(nèi)沒有找到一條最優(yōu)的路徑，則適當擴大范圍，并采用分塊加載數(shù)據(jù)的方法。采用矩形限制區(qū)域地圖數(shù)據(jù)選擇法并借助方向優(yōu)化，可以有效縮小搜索范圍，使得搜索結(jié)點的數(shù)量明顯小于全部結(jié)點數(shù)，提高了搜索的速度。（四）Dijkstra算法的優(yōu)化改進在經(jīng)典Dijkstra算法中，臨時標記結(jié)點無序地存儲在無序表中，這無疑成為Dijkstra算法的瓶頸。因為每次在臨時標記結(jié)點中搜索路徑最短的結(jié)點時，都要遍歷所有的臨時標記結(jié)點。解決辦法就是將臨時標記結(jié)點按照最

16、短路徑排序，每個搜索過程不必全部遍歷或者較少地遍歷臨時標記結(jié)點。為了減少最短路徑分析過程中搜索的臨時結(jié)點數(shù)量，盡快到達目標結(jié)點，優(yōu)化Dijkstra算法利用二叉排序樹，減少更新T集合的時間。二叉排序樹是利用二叉樹的結(jié)構(gòu)特點來實現(xiàn)對元素排序的。二叉排序樹的構(gòu)造過程實質(zhì)上就是排序的過程，它以二叉排序樹作為媒介，將一個任意的數(shù)據(jù)序列編程一個有序序列。二叉排序樹的構(gòu)造一般是采用陸續(xù)插入結(jié)點的辦法逐步構(gòu)成的。二叉排序樹構(gòu)造的思路為：以待排序的數(shù)據(jù)的第一個數(shù)據(jù)為根節(jié)點；對以后的各個數(shù)據(jù)，逐個插入結(jié)點；插入過程服從規(guī)定“在每次插入時，原有樹結(jié)點位置不變，只是將新數(shù)據(jù)的結(jié)點作為一個葉結(jié)點插入到合適的位置，使二

17、叉樹中任何結(jié)點的數(shù)據(jù)與其左右子樹結(jié)點數(shù)據(jù)之間的關系仍然符合二叉排序樹”。為了將二叉排序樹結(jié)構(gòu)應用于Dijkstra算法，主要是以起點到選擇的結(jié)點距離作為關鍵字，建立二叉排序樹。每次從二叉排序樹的最左下的葉結(jié)點取得最小值結(jié)點，將該結(jié)點加入集合S中，并從二叉排序樹中刪除該結(jié)點。之后以該節(jié)點為永久標記結(jié)點，計算該結(jié)點到T集合中各個結(jié)點的距離，如果該距離小于關鍵字，則將原來的結(jié)點刪除，更新關鍵字。二叉排序樹中的結(jié)點的具體數(shù)據(jù)結(jié)構(gòu)為：struct Nodelong nodeID; /結(jié)點索引號long distance; /源點到該節(jié)點的距離，作為關鍵字struct node *left_child,

18、*right_child; /結(jié)點的左右子結(jié)點struct node *parent; /結(jié)點的父結(jié)點綜合上述三個方面的改進，得到了基于矩形限制區(qū)域的二叉排序樹改進Dijkstra算法，流程如圖3所示。圖3 基于矩形限制區(qū)域的二叉排序樹改進Dijkstra算法流程圖四、算法分析及測試本文對地圖數(shù)據(jù)采取分塊加載的策略，使用矩形限制區(qū)域并借助趨勢方向優(yōu)化，見笑了搜索的范圍和結(jié)點的數(shù)目。改進的Dijkstra算法使得最短路徑搜索過程不再盲目，而是在方向上趨向終點。改進算法的時間復雜度主要耗費在生成二叉排序樹以及在二叉排序樹上插入結(jié)點。從空樹出發(fā)，通過將n個結(jié)點逐個查找并插入，可生成一個二叉排序樹，每

19、個結(jié)點插入的時間復雜度平均為O(lbn)，生成二叉樹的時間復雜度則為O(nlbn)，所以總的時間復雜度為O(nlbn)，比起經(jīng)典Dijkstra算法的O(n2)要降低不少；另外，采取鄰接結(jié)點存儲法使得空間復雜度由原來的O(n2)降低到O(n)。因此，從理論上來說，算法的優(yōu)化取得了良好的效果。本文采用以下嵌入式系統(tǒng)環(huán)境對改進算法進行了測試：操作系統(tǒng)為Windows CE，CPU為Intel 2.0 GHz，運行內(nèi)存為1GB，開發(fā)工具為Visual Studio，編程語言為C#。實現(xiàn)了對北京市地圖Dijkstra算法最短路徑求取的仿真實驗，證明該算法計算最短路徑是高效且具有較強魯棒性的。如圖4所示

20、是將給予矩形限制區(qū)域的二叉排序樹改進Dijkstra算法應用于北京市地圖查詢系統(tǒng)中的一個應用實例（小于1000條弧段，查詢道路時間<1/5s），圖中紫色的線段表示生成的最短路徑。圖5顯示的是該算法的效率。圖4 基于改進Dijkstra的GIS路徑分析算法結(jié)果示例圖圖5 改進Dijkstra算法的效率比較五、總結(jié)本文首先闡述了經(jīng)典Dijkstra算法的原理及缺陷，并在此基礎上，提出了改進的最短路徑算法基于矩形限制區(qū)域的二叉排序樹改進Dijkstra算法。該算法使用鄰接結(jié)點結(jié)構(gòu)，節(jié)省了內(nèi)存，可以應用于結(jié)點數(shù)巨大的網(wǎng)絡模型。采用矩形限制區(qū)域地圖數(shù)據(jù)選擇法并借助趨勢方向優(yōu)化，可以有效地縮小搜索范圍，減少了搜索結(jié)點的數(shù)目。使用二叉排序樹對最短路徑分析過程中搜索的臨時結(jié)點進行排序，減少了臨時結(jié)點的數(shù)量，加快了搜索進程。與傳統(tǒng)Dijkstra算法相比，改進算法有效地降低了算法的時間復雜度和空間復雜度。下一步有待研究的問題是需要更加周密地分