| k(≤3)条渐次最短路径搜索算法的研究及其实现技术 |
| |
| 引用本文： | 吴敏,苏厚勤,王明中.k(≤3)条渐次最短路径搜索算法的研究及其实现技术[J].计算机应用与软件,2004,21(8):81-83. |
| |
| 作者姓名： | 吴敏 苏厚勤 王明中 |
| |
| 作者单位： | 1. 上海市计算技术研究所,上海,200040
2. 上海华虹集团(有限)公司,上海,200051 |
| |
| 摘 要： | 目前针对“k(≤3)条渐次最短路径的问题”国际上尚无一种有效的解决方案，本文基于最短路径算法及背离路径的定义提出了一种递归计算方法，能够有效地解决某些实际问题中k条渐次最短路径的计算。对于算法中的环路问题，文中介绍了相应的方法予以消除。算法的复杂度分析及仿真实验表明本算法具有较好的性能。
|
| 关 键 词： | 最短路径搜索算法 对象模型 时间复杂性 TSP |
RESEARCH AND IMPLEMENTATION FOR THE ALGORITHM OF kTH APPOROCHING SHORTEST PATH |
| |
| Wu Min,Su Houqin,Wang Mingzhong.RESEARCH AND IMPLEMENTATION FOR THE ALGORITHM OF kTH APPOROCHING SHORTEST PATH[J].Computer Applications and Software,2004,21(8):81-83. |
| |
| Authors: | Wu Min Su Houqin Wang Mingzhong |
| |
| Affiliation: | Wu Min 1 Su Houqin 1 Wang Mingzhong 2 1 |
| |
| Abstract: | To the question of searching for k th shortest path,there is no resultful solution by far in the world.This paper introduced a recursive algorithm on the basis of shortest path algorithm and the definition of "deviation path".As for the cycle problem which involved in the algorithm,we also put forward a method to figure out.Complexity analysis and simulation results show that our algorithm has good performance. |
| |
| Keywords: | Shortest path Deviated path Weight Time-complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
