Dijkstra算法的分析与改进  

作　　者：王小虹 田文劲 陆毅 李永涛 

机构地区：[1]安徽师范大学皖江学院,安徽芜湖241000

出　　处：《移动信息》2021年第2期69-72,共4页MOBILE INFORMATION

基　　金：2020年度高等学校省级质量工程项目(项目号:S202013617006)。

摘　　要：文章是在基于传统 Dijkstra 算法的基础上,对现有 Dijkstra 算法进行分析与改进。传统的 Dijkstra 算法在解决单源最短路径的某些情况时,当存在负权边时,最短路径的权定义无效。并且 Dijkstra 算法是基于广度优先搜索的策略,这样就会使得 Dijkstra 运算效率低。为解决传统 Dijkstra 算法的不足,文章使用堆优化的Dijkstra 算法,使得算法的效率更高,时间复杂度更低。通过理论分析与实验测试结果可得,改进的 Dijkstra 算法的时间复杂度为 O(mlogn)。改进的 Dijkstra 算法大大提高了算法的效率和性能。

关 键 词：最短路径 DIJKSTRA算法 堆排序 邻接表 最优路径 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]