对Dijkstra算法的优化策略研究

• 作者: 丁豪杰 卢潇 陈益富
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最短路径算法 A*算法 Dijkstra算法 铁路两站点最优路径
• 年，卷（期）: 2006,（9）
• 所属期刊栏目: 智能、算法、软件工程
• 页码范围: 73-75,78
• 页数: 4页
• 分类号: TP301.6
• 字数: 3220字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2006.09.026

摘要

Dijkstra算法是许多工程解决最短路径问题的理论基础,但实际工程中涉及到的许多限制条件要求人们必须对该算法进行改进和优化.文中在对经典的Dijkstra算法思想进行分析的基础上,论述了Dijkstra算法的一种改进算--A*算法,并对它们之间的联系进行了剖析.在总结了一个实际工程项目开发的基础上,提出了一种基于Dijkstra算法上的针对铁路中两站点最优路径算法.文中提出的算法通过提取出铁路中的关键站点组成一个新图,之后将起点和终点插入到新图中,经过最多四次的排列组合后选出一个最短路径;该优化方法能将Dijkstra算法的时间复杂度o(n2)中的n降到一个很小的值.实践证明该方法在实际工程中完全可行且已取得了令人满意的效果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	卢潇	空军工程大学电讯工程学院	21	213	8.0	14.0
2	陈益富	空军工程大学电讯工程学院	1	60	1.0	1.0
3	丁豪杰	空军工程大学电讯工程学院	1	60	1.0	1.0