| 一种Dijkstra算法改进方法的研究与实现 |
| |
| 引用本文： | 刘刚,李永树,杨骏.一种Dijkstra算法改进方法的研究与实现[J].测绘科学,2011,36(4):233-235. |
| |
| 作者姓名： | 刘刚 李永树 杨骏 |
| |
| 作者单位： | 西南交通大学地理信息工程中心,成都,610031 |
| |
| 基金项目： | “十一五”国家科技支撑计划重大项目 |
| |
| 摘 要： | 从路径冗余角度研究了传统Dijkstra算法中的“交会路径”和“循环路径”问题,并针对上述问题提出了一种Dijkstra算法改进方法.该方法优化了路径搜索空间,降低了原算法的时间复杂度和空间复杂度,提高了算法的运行效率.最后,通过实验对该改进算法进行了验证.
|
| 关 键 词： | 最短路径分析 交会路径 循环路径 Dijkstra算法 |
Research and implementation on an improved method of Dijkstra algorithm |
| |
| LIU Gang,LI Yong-shu,YANG Jun.Research and implementation on an improved method of Dijkstra algorithm[J].Science of Surveying and Mapping,2011,36(4):233-235. |
| |
| Authors: | LIU Gang LI Yong-shu YANG Jun |
| |
| Institution: | (Geography Information Engineering Centre,Southwest Jiaotong University,Chengdu 610031,China) |
| |
| Abstract: | From the perspective of the path redundancy,focused on "Intersection Path" and "Loop Path" problems in Dijkstra algorithm,the paper proposed an improvement method of Dijkstra algorithm according to these problems.This method could optimize the path search space,decrease the original algorithm's time complexity and space complexity,and enhance the efficiency of the algorithm.And finally,the algorithm was validated through experiment. Key works:shortest path analysis;Intersection Path;Loop Path;Dijkstra algorithm |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
