任意两点最短路径算法的优化及实现

• 作者: 刘萍 涂亚平
• 来源期刊: 炮兵学院学报
• 学科: 工学
• 关键词: 最短路径 Dijkstra算法 最小堆 时间复杂度
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 基础理论与工程技术
• 页码范围: 91-94
• 页数: 4页
• 分类号: TP301.6
• 语种: 中文

摘要

求大规模复杂网络的最短路径问题,由于计算速度慢、需存储空间大,是与地理信息相关的应用系统经常遇到的"瓶颈"问题.在深入分析各种常用的最短路径算法的基础上,基于经典Dijksrta算法,从时间和空间优化角度,实现了计算任意两点间最短路径的优化算法.初步实验表明,优化后的算法,处理大规模复杂网络的最短路径问题比经典Dijksrta算法在时间上缩短了80%,在耗费的存储空间上减少了90%以上.