改进型Dijkstra算法的最短路径求解

• 作者: 方欢 方贤文 金婷
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: Dijkstra算法 前置邻结点 多条最短路径
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 应用技术与研究
• 页码范围: 129-131
• 页数: 3页
• 分类号: TP319
• 字数: 1365字
• 语种: 中文
• DOI: 10.11907/rjdk.1511199

摘要

最短路径问题一直是图论中的研究热点.为寻找有向图中任意两点之间存在的所有最短路径,从Dijkstra算法入手,分析其最短路径实现原理,发现其局限性,即多条路径求解是唯一的;对算法作出改进,在Dijkstra算法基础上引入前置邻结点,对每个顶点增加前置邻结点属性,并进行实时记录和更新,使改进后的算法能够求解多条路径问题.利用Java语言编程实现算法思想,通过简单的界面显示验证了算法的正确性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	方贤文	安徽理工大学理学院	124	250	10.0	12.0
2	方欢	安徽理工大学理学院	107	228	9.0	11.0
3	金婷	安徽理工大学理学院	1	10	1.0	1.0