摘要
在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.
出处
《中国图象图形学报》
CSCD
北大核心
2007年第5期922-926,共5页
Journal of Image and Graphics
基金
国家"863"高技术研究发展计划项目(2001AA1135210
2002AA114020)