基于配对堆改进的Dijkstra算法

摘要：

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

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

所属期刊栏目：12

分类号：P208(一般性问题)

资助基金：国家高技术研究发展计划863计划2001AA1135210;2002AA114020

在线出版日期：2007-06-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：922-926