首页 | 本学科首页   官方微博 | 高级检索  
     

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法
引用本文:陆锋,卢冬梅,崔伟宏.基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法[J].中国图象图形学报,1999,4(12).
作者姓名:陆锋  卢冬梅  崔伟宏
作者单位:中国科学院遥感应用研究所!北京100101
摘    要:在深入分析传统Dijkstra算法的基础上,提出了利用基于k 叉堆的优先级队列对算法进行改进的思想,并对3 种可合并堆进行了比较,从理论上证明了四叉堆在k 叉堆中的最优性,设计了基于四叉堆优先级队列及逆邻接表、顾及路段方向阻抗的改进型Dijkstra最短路径算法,将Dijkstra 算法复杂度降为O(nlogn)。针对GIS-T应用系统的动态特征,提出了Dijkstra 算法的逆序计算方法,通过构造逆序最短路径树,使算法更具灵活性和实用性

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

Improved Dijkstra Algorithm Based on Quad Heap Priority Queue and Inverse Adjacent List
Lu Feng,Lu Dongmei and Cui Weihong.Improved Dijkstra Algorithm Based on Quad Heap Priority Queue and Inverse Adjacent List[J].Journal of Image and Graphics,1999,4(12).
Authors:Lu Feng  Lu Dongmei and Cui Weihong
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 among k ary heap. The presented algorithm decreases the complexity of conventional Dijkstra algorithm to O (log n ). 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.
Keywords:Shortest path algorithm  Quad  heap  Priority queue  Geographic Information Systems
本文献已被 CNKI 等数据库收录!
点击此处可从《中国图象图形学报》浏览原始摘要信息
点击此处可从《中国图象图形学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号