资源描述：
《gis中使用改进的dijkstra算法实现最短路径的计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第5卷(A版)第12期中国图象图形学报Vol.5(A),No.122000年12月JournalofImageandGraphicsDec.2000GIS中使用改进的Dijkstra算法实现最短路径的计算唐文武施晓东朱大奎(南京大学海岸与海岛开发国家试点实验室海洋地理信息系统室,南京210093)摘要地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Dijkstra算法的基础上,采用二叉
2、堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了该算法的分析效率.讨论了地理网络数据的组织结构和最短路径的具体实现过程,并引入了相关概念.通过具体案例分析表明,改进算法在提高网络系统空间分析效率方面是可行的.关键词Dijkstra算法优先级队列二叉堆中图法分类号:P208文献标识码:A文章编号: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论理论中的网络图,并通过图论中的网络分析来实0引言现地理网络的最优化问题.在网络分析中,最短路径问题的分析是最基本近些年来,随着国际学术界加强了对GIS基础的,也是最关键的,如今,解决最短路径分析问题的方理论中空间关系的研究,地理网络分析的研究也有法虽然已经很成熟,例如以Dijkstra算法为代表的宽[1]了极大的发展.度优先搜索方法、动态规划方法等等,但作为网络分网络分析包括最短路径分析、资源配置、等时性析的关键环节,由于网络分析的存储量和计算量过于
8、问题等等,但在进行网络分析时,还要根据不同的网庞大,算法的效率将直接影响到整个系统的性能.因络,建立起相应的网络分析模型.这里,所谓网络模[2～5]此对该算法效率的改进历来是人们研究的热点.型,是指将现实中的地理网络实体,抽象化为网络图本文针对上述问题,在最短路径分析的经典算法收稿日期:2000201214;改回日期:20002042201020中国图象图形学报第5卷(A版)(即Dijkstra算法)的基础上,对网络的数据结构和计点间的最短路径包含了其内部其它的最短路
