改進(jìn)的Dijkstra算法

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

2、際數(shù)據(jù)測(cè)試也表明了該算法的有效性。關(guān)鍵詞：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（一）改進(jìn)的方面2（二）網(wǎng)絡(luò)路徑優(yōu)化的拓?fù)浣Y(jié)構(gòu)3（三）限制搜索區(qū)域加載部分網(wǎng)絡(luò)模型4（四）Dijkstra算法的優(yōu)化改進(jìn)5四、算法分析及測(cè)試7五、總結(jié)8參考文獻(xiàn)9一、引言隨著無(wú)線網(wǎng)絡(luò)的普及和智能移動(dòng)設(shè)備的發(fā)展，嵌入式移動(dòng)終端成為空間信息服務(wù)的核心組成和數(shù)字

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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