基于配对堆改进的Dijkstra算法

在GIS网络分析系统中,Dijkstra算法是求解最短路径的经典算法。为了进一步提高求解最短路径的效率和节省系统的内存空间,提出了使用一种新式的数据结构——配对堆,以便通过实现可降级的优先队列来改进Dijkstra算法,然后通过研究配对堆的基本操作,给出了使用配对堆结构实现Dijkstra算法的方法和流程,并分析了其算法复杂度。该算法在VegaGIS系统中实现,取得到了较好的效果。

An Improved Dijkstra Algorithm Based on Pairing Heap

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.