基于配对堆改进的Dijkstra算法

An Improved Dijkstra Algorithm Based on Pairing Heap

在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.