|
|||||
|
|
| Dijkstra最短路径算法优化策略 | |
| 引用本文： | 张锦明,洪刚,文锐,王学涛.Dijkstra最短路径算法优化策略[J].测绘科学,2009,34(5). |
| 作者姓名： | 张锦明 洪刚 文锐 王学涛 |
| 作者单位： | 1. 信息工程大学测绘学院,郑州,450052 2. 61363部队,西安,710054 3. 73603部队,南京,210049 |
| 摘 要： | 从分析经典Dijkstra最短路径算法出发,找出影响其效率的关键步骤:存储空间和时间效率,并结合当前已有的各种优化算法,总结出Dijkstra最短路径算法的优化策略:相关边优化策略、相关邻接结点优化策略、结点分类优化策略、权值排序优化策略、结点排序优化策略和单链结点剔除优化策略。最后,以实例运算表明优化策略是有效的,既节约了存储空间又提高了时间效率。 |
| 关 键 词： | 最短路径 Dijkstra算法 优化策略 |
Optimization strategies of the Dijkstra's shortest route algorithm |
|
| ZHANG Jin-ming,HONG Gang,WEN Rui,WANG Xue-tao.Optimization strategies of the Dijkstra's shortest route algorithm[J].Science of Surveying and Mapping,2009,34(5). | |
| Authors: | ZHANG Jin-ming HONG Gang WEN Rui WANG Xue-tao |
| Abstract: | After analysis of classical Dijkstra's algorithm,the key factors that influence the efficiency are storage space and time efficiency.Some optimization strategies of the Dijkstra's shortest route algorithm are concluded by combination of some existing algorithms,which include optimization strategy of related line,near nodes,node classification,weight value ordering,node ordering and one-chain node elimination.Examples of application prove that all the optimization strategies function well and can improve both storage space and time efficiency. |
| Keywords: | shortest route Dijkstra's algorithms optimization strategies |
| 本文献已被 万方数据 等数据库收录！ | |