[1]陈益富 卢潇 丁豪杰.对Dijkstra算法的优化策略研究[J].计算机技术与发展,2006,(09):73-75.
　CHEN Yi-fu,LU Xiao,DING Hao-jie.Optimized Strategy Research over Algorithm of Dijkstra[J].,2006,(09):73-75.
点击复制

对Dijkstra算法的优化策略研究()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2006年09期
页码:
73-75
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Optimized Strategy Research over Algorithm of Dijkstra
文章编号:
1673-629X（2006）09-0073-03
作者:
陈益富 卢潇 丁豪杰
空军工程大学电讯工程学院
Author(s):
CHEN Yi-fu;  LU Xiao; DING Hao-jie
Telecommunication Engineering Institute, Air Force Engineering University
关键词:
最短路径算法; A＊算法; Dijkstra算法; 铁路两站点最优路径
Keywords:
the shortest path algorithm; A ＊ algorithm;  algorithm of Dijkstra; the best path between two railway stations
分类号:
TP301.6
文献标志码:
A
摘要:
Dijkstra算法是许多工程解决最短路径问题的理论基础，但实际工程中涉及到的许多限制条件要求人们必须对该算法进行改进和优化。文中在对经典的Dijkstra算法思想进行分析的基础上，论述了Dijkstra算法的一种改进算法——A＊算法，并对它们之间的联系进行了剖析。在总结了一个实际工程项目开发的基础上，提出了一种基于Dijkstra算法上的针对铁路中两站点最优路径算法。文中提出的算法通过提取出铁路中的关键站点组成一个新图，之后将起点和终点插入到新图中，经过最多四次的排列组合后选出一个最短路径；该优化方法能将Dijkstra算法的时间复杂度o（n^2）中的n降到一个很小的值。实践证明该方法在实际工程中完全可行且已取得了令人满意的效果
Abstract:
The algurithm of Dijkstra is academic foundation that many engineerings were solved in the shortest path issue, but people must improve and optimize to this algorithm what involves many limitative condition in the real engineering. So makes a summary on the foundation analysed to the algorithm of Dijkstra thought of classics, and discussed one kind of algorithm improving the algorithm of Dijkstra called A ＊ Algorithm, to dissect the contact between them. On sum up the foundation of a real project, put forward based on being directed agaiust railway two stations the shortest path algorithm on the algorithm of Dijkstra. The algorithm that was made in this article is put forward a new figure by way drawing out the hinge station in the railway. Afterwards ,inserting starting station and terminal station to the new figure, you can .select out the shortest path of railway after the combination of unexcelled four times the range. The optimized method can fall n value with the algorithm of Dijkstra of the time complexity o （ n2 ） to a very small value. The practice proves this method is feasible completely in the real engineering and has taken satisfied effect

相似文献/References:

[1]郑延斌 李新源 段德全.一种保持Agent团队队形的路径规划方法[J].计算机技术与发展,2009,(07):159.
　ZHENG Yan-bin,LI Xin-yuan,DUAN De-quan.A Path Planning Algorithm with Agent Team Formation Maintained[J].,2009,(09):159.
[2]冯晓辉 马光思.数码谜题求解的算法设计及其扩展研究[J].计算机技术与发展,2009,(08):110.
　FENG Xiao-hui,MA Guang-si.Algorithm Design and Extension Research of N - Puzzle Problem[J].,2009,(09):110.
[3]李培 何中市.基于ArcGIS和GPS的水电气管理系统设计与实现[J].计算机技术与发展,2009,(01):172.
　LI Pei,HE Zhong-shi.Design and Implementation Water, Electricity and Gas Management System Based on ArcGIS and GPS[J].,2009,(09):172.
[4]朱永红 张燕平.用VC＋＋实现基于A＊算法的八数码问题[J].计算机技术与发展,2006,(09):32.
　ZHU Yong-hong,ZHANG Yan-ping.Programming for Eight - Figure Puzzle Problem Based on Algorithm A ＊ with Visual C ＋ ＋[J].,2006,(09):32.
[5]方伟华.基于A＊算法和图遍历的烟草物流VRP的研究[J].计算机技术与发展,2011,(12):63.
　FANG Wei-hua.Research on Tobacco Logistics VRP Based on A ＊ Algorithm and Graph Traversal[J].,2011,(09):63.
[6]刘钰 陆建峰 蔡海舟.基于改进A＊算法的机器人路径规划方法研究[J].计算机技术与发展,2012,(12):108.
　LIU Yu,LU Jian-feng,CAI Hai-zhou.Research on Path Planning Method of Robot Based on Improved A ＊ Algorithm[J].,2012,(09):108.
[7]张英辉,张水平,张凤琴,等.基于OpenStreetMap最短路径算法的分析与实现[J].计算机技术与发展,2013,(11):37.
　ZHANG Ying-hui,ZHANG Shui-ping,ZHANG Feng-qin,et al.Analysis and Implementation of Shortest Path Algorithm Based on OpenStreetMap[J].,2013,(09):37.
[8]孙强 戴志军.用元胞自动机求最短路径的一种新算法[J].计算机技术与发展,2009,(02):42.
　SUN Qiang,DAI Zhi-jun.A New Shortest Path Algorithm Using Cellular Automata Model[J].,2009,(09):42.
[9]马静,王佳斌,张雪. A*算法在无人车路径规划中的应用[J].计算机技术与发展,2016,26(11):153.
　MA Jing,WANG Jia-bin,ZHANG Xue. Application of A* Algorithm in Unmanned Vehicle Path Planning[J].,2016,26(09):153.
[10]朱云虹,袁一.基于改进A*算法的最优路径搜索[J].计算机技术与发展,2018,28(04):55.[doi:10.3969/ j. issn.1673-629X.2018.04.012]
　ZHU Yun-hong,YUAN Yi.Optimal Path Search Based on Improved A* Algorithm[J].,2018,28(09):55.[doi:10.3969/ j. issn.1673-629X.2018.04.012]

备注/Memo

备注/Memo:
陈益富（1972-），男，江苏盐城人，硕士研究生，研究方向为计算机网络与数据库技术；卢潇，副教授，研究领域为算法分析与数据库技术
更新日期/Last Update: 1900-01-01