基于配对堆改进的Dijkstra算法  

An Improved Dijkstra Algorithm Based on Pairing Heap

作　　者：张林广[1] 方金云[1] 申排伟[1] 

机构地区：[1]中国科学院计算技术研究所空间信息处理技术实验室,北京100080

出　　处：《中国图象图形学报》2007年第5期922-926,共5页Journal of Image and Graphics

基　　金：国家"863"高技术研究发展计划项目(2001AA1135210;2002AA114020)

摘　　要：在GIS网络分析系统中,Dijkstra算法是求解最短路径的经典算法。为了进一步提高求解最短路径的效率和节省系统的内存空间,提出了使用一种新式的数据结构——配对堆,以便通过实现可降级的优先队列来改进Dijkstra算法,然后通过研究配对堆的基本操作,给出了使用配对堆结构实现Dijkstra算法的方法和流程,并分析了其算法复杂度。该算法在VegaGIS系统中实现,取得到了较好的效果。Dijkstra is a classic algorithm to compute the shortest-path in GIS network analysis system. To improve the algorithm efficiency and save memory usage, this paper proposes a new data structure, called ＂pairing heap＂, to implement the priority queue. So that the Dijkstra algorithm can use pairing heap. This paper gives out the implementation details and algorithm＇ s flow via studying the basic function of paring heap, and then analyses the algorithm＇ s complexity. This new algorithm has applied in VegaGIS and obtains good results.

关 键 词：DIJKSTRA 最短路径 优先队列 配对堆 织女星地理信息系统 

分 类 号：P208[天文地球—地图制图学与地理信息工程]