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

陆锋; 卢冬梅; 崔伟宏

doi:10.11834/jig.1999012250

学术论文与技术报告 | 浏览量 : 0 下载量: 132 CSCD: 0

PDF
导出
分享
收藏
专辑

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算法
Improved Dijkstra Algorithm Based on Quad-Heap Priority Queue and Inverse Adjacent List
1999年4卷第12期页码：1044
纸质出版：1999
DOI： 10.11834/jig.1999012250
稿件说明：

移动端阅览

陆锋, 卢冬梅, 崔伟宏. 基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算法[J]. 中国图象图形学报, 1999,4(12):1044. DOI： 10.11834/jig.1999012250.

Improved Dijkstra Algorithm Based on Quad-Heap Priority Queue and Inverse Adjacent List[J]. Journal of Image and Graphics, 1999, 4(12): 1044. DOI： 10.11834/jig.1999012250.

摘要

在深入分析传统Dijkstra算法的基础上，提出了利用基于ｋ叉堆的优先级队列对算法进行改进的思想，并对3种可合并替进行了比较，从理论上证明了四叉堆在ｋ叉堆中的最优性，设计了基于四叉堆优先级队列及逆领接表，顾及路段方向阻抗的改进型Dijkstra最短径算法，将Dijkstra算法复杂度降为O(nlogn)。

Abstract

An improved Dijkstra algorithm is set forward on the basis of priority queue based on quad-heap. It is proved in this paper that quad-heap is the optimum amongk-ary heap. The presented algorithm decreases the complexity of conventional Dijkstra algorithm toO(logn). Considering the dynamic characters of transportation applications

an inverse running sequence is presented based on the inverse adjacent list data structure. It is more suitable for the dynamic applications of GIS-T.