基于配对堆改进的Dijkstra算法

张林广; 方金云; 申排伟

发布时间：
摘要点击次数： 4402
全文下载次数： 300
DOI: 10.11834/jig.20070526
2007 | Volume 12 | Number 5

基于配对堆改进的Dijkstra算法

张林广¹, 方金云¹, 申排伟¹(中国科学院计算技术研究所空间信息处理技术实验室，北京 100080)

摘要

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

关键词

Dijkstra 最短路径优先队列配对堆织女星地理信息系统

An Improved Dijkstra Algorithm Based on Pairing Heap

()

Abstract

Keywords

Dijkstra shortest-path priority queue paring heap VegaGIS

在线采编平台

论文出版

年度会议

下载中心

年度信息