一种基于Dijkstra最短路径算法的改进算法

• 作者: 李妍 王兴会 王智广
• 来源期刊: 内蒙古师范大学学报（自然科学汉文版）
• 学科: 工学
• 关键词: Dijkstra算法 路网 邻接表 反向N叉树 最短路径
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 195-200
• 分类号: TP319
• 字数: 3495字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-8735.2012.02.018

摘要

Dijkstra算法是求解最短路径的经典算法,是在许多应用中解决最短路径问题的理论基础,但实际应用中涉及的许多限制条件要求人们必须对该算法进行改进和优化.在分析经典Dijkstra算法思想的基础上,给出Dijkstra算法的一种改进算法.在该算法中图的存储表示采用邻接表的方式,避免邻接矩阵在工程应用中的局限性.在最短路径的计算过程中,采用优先级队列与反向N叉树相结合的方式,以便通过实现可降级的优先队列来改进Dijkstra算法.给出了改进形Dijkstra算法的方法和流程,分析了其算法复杂度,并对改进后的算法进了详细的分析和测试.