dijkstra算法在gis實(shí)際應(yīng)用中的優(yōu)化

《dijkstra算法在gis實(shí)際應(yīng)用中的優(yōu)化》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、Dijkstra算法在GIS實(shí)際應(yīng)用中的優(yōu)化摘要：地理信息系統(tǒng)（GIS）的實(shí)際應(yīng)用中，對城市道路最短路徑的搜索一直是人們研究的重點(diǎn)。Dijkstra算法是最適合拓?fù)鋁絡(luò)中兩點(diǎn)間最短路徑搜索的算法之一，但由于在城市里對道路最短路徑搜索受到道路的暢通等原因所影響，故單純利用Dijkstra算法并不能很好解決人們的實(shí)際需求。本文通過在GIS系統(tǒng)中增加一個(gè)設(shè)置、查詢路障功能來解決以上提到的問題。關(guān)鍵詞：Dijkstra；算法；優(yōu)化1.引言近年來，GIS被廣泛的應(yīng)用在城市管理等方面上，GIS最主要、最具體的任務(wù)是負(fù)責(zé)管理大型X狀設(shè)施(如城市中的各類地下管線、交通線、通訊線路等)

2、，使得其對X絡(luò)最短路徑分析功能的需求日益增長。在對最短路徑搜索的問題上，Dijkstra算法是綜合各方面性能較好的算法之一?？稍趯?shí)際道路搜索中，最短路徑的意義不僅是指地理上的最短距離，還應(yīng)包括時(shí)間上的，即能用最短的時(shí)間到達(dá)目的路，這對安排搶險(xiǎn)救援的路線尤其重要。本文針對城市應(yīng)急中的最短路徑分析進(jìn)行了深入的研究，并提出了相應(yīng)的解決辦法。2.Dijkstra算法的應(yīng)用與實(shí)現(xiàn)傳統(tǒng)的Dijkstra算法將X絡(luò)節(jié)點(diǎn)分為未標(biāo)記結(jié)點(diǎn)、臨時(shí)結(jié)點(diǎn)和永久標(biāo)記結(jié)點(diǎn)三種類型。X絡(luò)中所有結(jié)點(diǎn)首先初始化為未標(biāo)記結(jié)點(diǎn)，在搜索過程中和最短路徑結(jié)點(diǎn)相連通的節(jié)點(diǎn)為臨時(shí)標(biāo)記結(jié)點(diǎn)，每一次循環(huán)都是從臨時(shí)標(biāo)記結(jié)

3、點(diǎn)中搜索距離源點(diǎn)路徑長度最短的結(jié)點(diǎn)作為永久標(biāo)記結(jié)點(diǎn)，直至找到目標(biāo)結(jié)點(diǎn)或者所有結(jié)點(diǎn)都成為永久標(biāo)記結(jié)點(diǎn)才結(jié)束算法。該算法能有效解決有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題。在本文討論的GIS中，用MapObjects實(shí)現(xiàn)的具體思路為：(1)在地圖上獲取一點(diǎn)，作為起點(diǎn)，并獲取到該點(diǎn)的點(diǎn)對象FMoPoint。(2)以FMoPoint作為源點(diǎn)調(diào)用MO的方法對指定的單位圖層搜索該點(diǎn)附近很小范圍內(nèi)的圖元元素，搜索到的第一個(gè)圖元元素作為起點(diǎn)的起始地址；若搜索不到，則把步驟(3)得到的道路名稱作為起始地址。(3)以FMoPoint作為源點(diǎn)調(diào)用MO的方法搜索最短路徑圖層，找到距離原點(diǎn)最近

4、的一條道路作為開始的道路。具體的搜索的方法為：①以某一指定的步長作為搜索范圍的半徑，搜索FMoPoint作為圓點(diǎn)的圓形范圍；搜索的結(jié)果若為空，則增加步長的值，再重新開始搜索，直到搜索結(jié)果不為空。②將搜索到的結(jié)果作為一個(gè)線段的集合，計(jì)算源點(diǎn)到每條線段的最短距離，距離源點(diǎn)最近的一條線段作為開始的線段（道路），并記錄下該線段到源點(diǎn)距離最短的點(diǎn)作為FNode（開始結(jié)點(diǎn)）。(4)同理，在地圖上獲取第二點(diǎn)TMoPoint作為終點(diǎn)，并得到終點(diǎn)的地址，和終點(diǎn)（結(jié)束）的線段（道路）及TNode（結(jié)束結(jié)點(diǎn)）。(5)得到開始線段和結(jié)束線段后，計(jì)算出FNode到開始線段的兩個(gè)端點(diǎn)的距離，TN

5、ode到結(jié)束線段兩個(gè)端點(diǎn)的距離；因?yàn)镕Node和TNode是作為臨時(shí)創(chuàng)建的點(diǎn)，故要計(jì)算出所需的距離，用于最短距離計(jì)算。(6)以FNode作為起點(diǎn)，TNode作為終點(diǎn)，用Dijkstra算法對最短路徑圖層計(jì)算出最短路徑來。(7)判斷FMoPoint是否在開始線段上，如果不在則計(jì)算FMoPoint到FNode的距離；如果在，則計(jì)算實(shí)際的最短路徑由FMoPoint經(jīng)過開始線段的端點(diǎn)的距離。(8)同理，判斷TMoPoint是否在結(jié)束線段上，并進(jìn)行相應(yīng)的處理。最后調(diào)整最短路徑的實(shí)際距離。最短路徑計(jì)算結(jié)束。3.改進(jìn)的設(shè)計(jì)與實(shí)現(xiàn)由于上述算法中得到只是行駛長度的最短路徑，但在實(shí)際情況

6、中，這個(gè)長度并不真正就意味著是救援者到現(xiàn)場的最優(yōu)路徑，因這其中還涉及到道路等級、路面狀況等因素。為此本系統(tǒng)還增加了一個(gè)設(shè)置路障、查詢路障的功能，使查找最短路徑時(shí)能避開這些無效路徑，從而得到實(shí)際中的最優(yōu)路徑。實(shí)現(xiàn)的具體思路為：(1)首先得到要設(shè)置的道路，方法有兩個(gè)：①通過MO的方法用SQL語句來查詢所要設(shè)置的道路。②通過點(diǎn)取地圖上的道路線段來獲得所要設(shè)置的線段。實(shí)現(xiàn)為在地圖上點(diǎn)一點(diǎn)，然后調(diào)用MO的搜索方法搜索該點(diǎn)附近的線段來獲取要設(shè)置的線段。(2)得到要設(shè)置的道路線段后，通過MO的方法獲得該線段兩個(gè)端點(diǎn)的經(jīng)緯度。計(jì)算這兩點(diǎn)的經(jīng)度值之差的絕對值（LongV）和緯度值之差的

7、絕對值（LatV）。比較LongV和LatV的大小，如果LongV>LatV，那么認(rèn)為該道路線段是沿著經(jīng)度方向的，反之，則認(rèn)為該道路線段是沿著緯度方向的。(3)MO的每條線段都是點(diǎn)的集合，假定對應(yīng)數(shù)組PointAry[i](i=0,1,2,……,PointCount-1)，并且把PointAry[0]當(dāng)作該線段的起點(diǎn)，把PointAry[PointCount-1]當(dāng)作終點(diǎn)。如果起點(diǎn)的緯度值大于終點(diǎn)的緯度值，則該線段默認(rèn)的緯度方向是從東向西，反之，則是從西向東。同理，如果起點(diǎn)的經(jīng)度值大于終點(diǎn)的經(jīng)度值，則該線段默認(rèn)的經(jīng)度方向是從北朝南，反之，則是從南朝北