基于配对堆改进的Dijkstra算法

被引：16

作者：

张林广

方金云

申排伟

机构：

[1] 中国科学院计算技术研究所空间信息处理技术实验室

来源：

中国图象图形学报 | 2007年 / 05期

关键词：

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

D O I：

暂无

中图分类号：

U116.2 [运输线路优选]; P208 [测绘数据库与信息系统];

学科分类号：

08 ; 0823 ; 070503 ; 081603 ; 0818 ; 081802 ;

摘要：

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

引用

页码：922 / 926

页数：5

共 5 条

[1] GIS领域最短路径搜索问题的一种高效实现 [J].

王开义 ;

赵春江 ;

胥桂仙 ;

宋晓宇 .

中国图象图形学报, 2003, (08) :105-110

[2] 基于GIS的城市道路网最短路径算法探讨 [J].

严寒冰 ;

刘迎春 .

计算机学报, 2000, (02) :210-215

[3] 交通网络限制搜索区域时间最短路径算法 [J].

陆锋 ;

卢冬梅 ;

崔伟宏 .

中国图象图形学报, 1999, (10) :47-51

[4]

The pairing heap: A new form of self-adjusting heap[J] . Michael L. Fredman,Robert Sedgewick,Daniel D. Sleator,Robert E. Tarjan.Algorithmica . 1986 (1)

[5]

Shortest paths in euclidean graphs[J] . Robert Sedgewick,Jeffrey Scott Vitter.Algorithmica . 1986 (1)

← 1 →