基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法

被引：37

作者：

陆锋

卢冬梅

崔伟宏

机构：

[1] 中国科学院遥感应用研究所!北京

来源：

中国图象图形学报 | 1999年 / 12期

关键词：

最短路径算法; 四叉堆; 优先级队列; 地理信息系统;

D O I：

暂无

中图分类号：

U491 [交通工程与交通管理];

学科分类号：

082302 ; 082303 ;

摘要：

在深入分析传统Ｄｉｊｋｓｔｒａ算法的基础上，提出了利用基于ｋ叉堆的优先级队列对算法进行改进的思想，并对３种可合并堆进行了比较，从理论上证明了四叉堆在ｋ叉堆中的最优性，设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Ｄｉｊｋｓｔｒａ最短路径算法，将Ｄｉｊｋｓｔｒａ算法复杂度降为Ｏ（ｎｌｏｇｎ）。针对ＧＩＳ－Ｔ应用系统的动态特征，提出了Ｄｉｊｋｓｔｒａ算法的逆序计算方法，通过构造逆序最短路径树，使算法更具灵活性和实用性

引用

页码：32 / 38

页数：7