資源描述：
《Dijkstra最短路徑分析算法的優(yōu)化實現(xiàn).pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第37卷第5期測繪與空間地理信息Vo1．37，No．52014年5月GEoMATlCs＆SPATlALlNFORMATloNTECHNOLOGYMay．，2014Dijkstra最短路徑分析算法的優(yōu)化實現(xiàn)李妍妍(遼寧省基礎(chǔ)測繪院，遼寧錦州121003)摘要：最短路徑問題是地理信息系統(tǒng)的關(guān)鍵問題，傳統(tǒng)Dijkstra算法在求解節(jié)點間最短路徑時，對已標識節(jié)點以外的大量節(jié)點進行了計算，從而影響了算法的速度。因而對其算法進行優(yōu)化是很有必要。本文在對傳統(tǒng)Dijk—stra算法分析的基礎(chǔ)上，對其進行了優(yōu)化，優(yōu)化算法只對最短路徑上節(jié)點的鄰居做了處理，而不涉及其他節(jié)點，并利用VisualC++6．0開發(fā)平臺
2、編程進行了實驗。實驗表明，該算法是行之有效的。關(guān)鍵詞：Dijkstra算法；最短路徑；地理信息系統(tǒng)中圖分類號：P25；TP301．6文獻標識碼：文章編號：1672—5867(2014)05—0172—02TheOptimizationAlgorithmDijkstraImplementationofShortestpathAnalysisLIYan—yan(LiaoningProvinceBasedSurveyingandMappingInstitute，Jinzhou121003，C~na)Abstract：Theshortestpathproblemisakeyissueingeogra
3、phicinformationsystem，thetraditionalDijkstraalgorithmforsolvingtheshortestpathbetweennodes，thenodesidentifiednumerousoutsidewascalculated，whichafectsthespeedofthealgorithm．Thasthealgorithmoptimizationisverynecessary．BasedontheanalysisoftraditionalDijkstraalgorithm，hascarriedontheoptimization，opti·m
4、izationalgorithmfortheshortestpathnodeneighborfortreatment，withoutinvolvingothernodes，andexperimentsarecarriedoutU—singVisualC++6．0software．Experimentsshowthat．thealgorithmisefective．Keywords：Dijkstraalgorithm；shortestpath；geographicinformationsystem0引言1經(jīng)典Dijkstra算法的基本原理地理網(wǎng)絡(luò)分析是GIS的一個主要功能?。它包括最最短路徑問
5、題是指在一個非負權(quán)值圖中找出兩個指短路徑分析、資源配置、等時性問題等，其中，最短路徑分定節(jié)點間的一條權(quán)值和最小的路徑。Dijkstra算法是經(jīng)典析是最基本的，也是最關(guān)鍵的。人們常想知道在地理空的解決最短路徑問題的算法，是按路徑長度遞增的次序間網(wǎng)絡(luò)的兩指定點間是否存在路徑，如果有則特別希望來產(chǎn)生最短路徑的算法。它可以找出指定節(jié)點到其他找出其中的最短路徑。這種最短路徑問題對于交通、消各個節(jié)點間的最短路徑，其主要思想是首先從源點求出防、信息傳輸、救災(zāi)、搶險等有著重要的意義，因而引起了長度最短的一條路徑，然后通過對路徑長度迭代得到從人們的極大興趣。源點到其他各目標節(jié)點的最短路徑?，F(xiàn)有的最短路徑算法有
6、許多，其中，Dijkstra算法由于1)假設(shè)用帶權(quán)的鄰接矩陣cost來表示一個帶權(quán)圖，cost[i，]表示弧<．>上的權(quán)值。若<>不存能適應(yīng)網(wǎng)絡(luò)拓撲的變化，性能穩(wěn)定，因而在計算機網(wǎng)絡(luò)拓，撲路徑選擇以及GIS中得到廣泛的應(yīng)用。但傳統(tǒng)的Dijk．在，則置cost[√]為oo(在計算機上可以用允許的最大整stra算法采用鄰接矩陣存儲網(wǎng)絡(luò)拓撲結(jié)構(gòu)，需要(N×N)數(shù)值來表示)，s已找到從n一1點出發(fā)的最短路徑的集的存儲空間，隨著節(jié)點數(shù)Ⅳ的增大，其計算效率和存儲效合，它的初態(tài)為空集。從到其他節(jié)點的路徑長度向量率降低。針對此問題，本文在對傳統(tǒng)Dijkstra算法分析的為dist[n]，那么從dist[n]
7、出發(fā)到圖上其余頂點可能基礎(chǔ)上，對其進行了優(yōu)化。優(yōu)化算法只對最短路徑上節(jié)達到的最短路徑長度的初值為：點的鄰居做處理，而不涉及其他節(jié)點。dist[]=cost[voi]，∈V收稿日期：2013一l1—21作者簡介：李妍妍(1981一)，女，遼寧彰武人，助理工程師，主要從事航測內(nèi)業(yè)工作。190測繪與空間地理信息2014年出版社．2005．5結(jié)束語楊生田，盧華．城鎮(zhèn)地籍測量中土地面積量算的精度控綜上所述，用坐標法計算
