| 最短路径算法的分析与优化 |
| |
| 引用本文： | 张建军,杜莉.最短路径算法的分析与优化[J].北京工业职业技术学院学报,2009,8(3):26-31. |
| |
| 作者姓名： | 张建军 杜莉 |
| |
| 作者单位： | 北京工业职业技术学院,北京,100042;北京工业职业技术学院,北京,100042 |
| |
| 基金项目： | 北京市属市管高等学校人才强教计划资助项目,项目编号:京教人[2006]29号 |
| |
| 摘 要： | 最短路径问题在交通、网络应用中具有很高的实用价值,最短路径搜索算法在空间和时间复杂度上有不同的特点,根据需求的现状合理选择搜索算法和改进经典算法是应用中的常规方法。由简单到复杂的分析了搜索最短路径的9种算法,并且比较了经典的Dijkstra算法和启发式搜索算法A＊的关系和特点,并且提出了提高搜索效率的改进方法。
|
| 关 键 词： | 最短路径 Dijkstra 图 A* |
Analysis and Optimization of Algorithm for Finding Shortest Path |
| |
| Zhang Jianjun,Du Li.Analysis and Optimization of Algorithm for Finding Shortest Path[J].Journal of beijing vocational & technical institute of industry,2009,8(3):26-31. |
| |
| Authors: | Zhang Jianjun Du Li |
| |
| Institution: | Beijing Polytechnic College;Beijing 100042;China |
| |
| Abstract: | Shortest path has high value of practical application to transport and network.The algorithm of finding the shortest path has different features in the complexity of time and space,so the conventional method is to reasonably choose or improve classical algorithm according to actual demand.From the simplest to the most complex,this paper analyzes 9 algorithms for finding the shortest path,compares the characteristics and relation of classical Dijkstra and heuristic A* algorithm,and brings forward a method of... |
| |
| Keywords: | shortest path Dijkstra graph A* |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
