資源描述：
《gis中使用改進(jìn)的dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第5卷(A版)第12期中國(guó)圖象圖形學(xué)報(bào)Vol.5(A),No.122000年12月JournalofImageandGraphicsDec.2000GIS中使用改進(jìn)的Dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算唐文武施曉東朱大奎(南京大學(xué)海岸與海島開發(fā)國(guó)家試點(diǎn)實(shí)驗(yàn)室海洋地理信息系統(tǒng)室,南京210093)摘要地理信息系統(tǒng)中的空間網(wǎng)絡(luò)分析有最短路徑分析、資源分配分析、等時(shí)性分析等等,而最短路徑分析是其中關(guān)鍵的環(huán)節(jié),因而對(duì)其算法進(jìn)行優(yōu)化很有必要,為此在傳統(tǒng)的最短路徑算法,即Dijkstra算法的基礎(chǔ)上,采用二叉
2、堆結(jié)構(gòu)來實(shí)現(xiàn)路徑計(jì)算過程中優(yōu)先級(jí)隊(duì)列的一系列操作,從而提高了該算法的分析效率.討論了地理網(wǎng)絡(luò)數(shù)據(jù)的組織結(jié)構(gòu)和最短路徑的具體實(shí)現(xiàn)過程,并引入了相關(guān)概念.通過具體案例分析表明,改進(jìn)算法在提高網(wǎng)絡(luò)系統(tǒng)空間分析效率方面是可行的.關(guān)鍵詞Dijkstra算法優(yōu)先級(jí)隊(duì)列二叉堆中圖法分類號(hào):P208文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):100628961(2000)1221019205TheCalculationoftheShortestPathUsingModifiedDijkstraAlgorithminGISTANGWen
3、2wu,SHIXiao2dong,ZHUDa2kui(MarineGISLaboratoryofStatePilotLaboratoryofCoastandIslandDevelopment,NanjingUniversity,Nanjing210093)AbstractInGISitisnecessarytooptimizetheanalysisfunctionoftheshortestpathasthehingeofspatialnetworkanalysis,whichincludesshor
4、testpathanalysis,resourceallocationandisochrone,andsoon.Herederivedfromthetraditionalcalculatingmethod,i.e.Dijkstraalgorithm,theanalysisprocedureoftheshortestpathisimprovedbyadoptingthedatastructureofbinaryheaptocompletetheoperationofpriorityqueue.Init
5、ialization,Extraction,andRelzxztion.Thetopologicalstructureofgeographicalnetworkdataandthedetailedimplementingstepsoftheshortestpatharealsodiscussed.Furthermore,thevisualizingcalculationoftheshortestpathiscompletedbyCOM(ComponentObjectModel)techniques,
6、andthecalculatingprocedureisencapsulatedintothecomponentofthegeographicnetworkclass.Thecomplexityanalysisandthecaseofthisalgorithmshowesthatthemodifiedalgorithmisapplicabletoimprovetheefficiencyofspatialanalysisofthenetsystem.KeywordsDijkstraalgorithm,
7、Priorityqueue,Binaryheap論理論中的網(wǎng)絡(luò)圖,并通過圖論中的網(wǎng)絡(luò)分析來實(shí)0引言現(xiàn)地理網(wǎng)絡(luò)的最優(yōu)化問題.在網(wǎng)絡(luò)分析中,最短路徑問題的分析是最基本近些年來,隨著國(guó)際學(xué)術(shù)界加強(qiáng)了對(duì)GIS基礎(chǔ)的,也是最關(guān)鍵的,如今,解決最短路徑分析問題的方理論中空間關(guān)系的研究,地理網(wǎng)絡(luò)分析的研究也有法雖然已經(jīng)很成熟,例如以Dijkstra算法為代表的寬[1]了極大的發(fā)展.度優(yōu)先搜索方法、動(dòng)態(tài)規(guī)劃方法等等,但作為網(wǎng)絡(luò)分網(wǎng)絡(luò)分析包括最短路徑分析、資源配置、等時(shí)性析的關(guān)鍵環(huán)節(jié),由于網(wǎng)絡(luò)分析的存儲(chǔ)量和計(jì)算量過于
8、問題等等,但在進(jìn)行網(wǎng)絡(luò)分析時(shí),還要根據(jù)不同的網(wǎng)龐大,算法的效率將直接影響到整個(gè)系統(tǒng)的性能.因絡(luò),建立起相應(yīng)的網(wǎng)絡(luò)分析模型.這里,所謂網(wǎng)絡(luò)模[2～5]此對(duì)該算法效率的改進(jìn)歷來是人們研究的熱點(diǎn).型,是指將現(xiàn)實(shí)中的地理網(wǎng)絡(luò)實(shí)體,抽象化為網(wǎng)絡(luò)圖本文針對(duì)上述問題,在最短路徑分析的經(jīng)典算法收稿日期:2000201214;改回日期:20002042201020中國(guó)圖象圖形學(xué)報(bào)第5卷(A版)(即Dijkstra算法)的基礎(chǔ)上,對(duì)網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)和計(jì)點(diǎn)間的最短路徑包含了其內(nèi)部其它的最短路
