|
|||||
|
|
| 基于配对堆改进的Dijkstra算法 | |
| 作者姓名： | 张林广 方金云 申排伟 |
| 作者单位： | 中国科学院计算技术研究所空间信息处理技术实验室 北京100080 |
| 基金项目： | 国家高技术研究发展计划(863计划) |
| 摘 要： | 在GIS网络分析系统中,Dijkstra算法是求解最短路径的经典算法。为了进一步提高求解最短路径的效率和节省系统的内存空间,提出了使用一种新式的数据结构——配对堆,以便通过实现可降级的优先队列来改进Dijkstra算法,然后通过研究配对堆的基本操作,给出了使用配对堆结构实现Dijkstra算法的方法和流程,并分析了其算法复杂度。该算法在VegaGIS系统中实现,取得到了较好的效果。 |
| 关 键 词： | 最短路径 优先队列 配对堆 织女星地理信息系统 |
| 文章编号： | 1006-8961（2007）05-0922-05 |
| 收稿时间： | 2006-02-10 |
| 修稿时间： | 2006-05-08 |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |