| 一种新的Kth最短路径搜索算法 |
| |
| 引用本文： | 王明中,谢剑英,陈应麟.一种新的Kth最短路径搜索算法[J].计算机工程与应用,2004,40(30):49-50,89. |
| |
| 作者姓名： | 王明中 谢剑英 陈应麟 |
| |
| 作者单位： | 上海交通大学自动化系,上海,200030 |
| |
| 摘 要： | 借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。
|
| 关 键 词： | Kth最短路径 最短路径 “背离”路径 |
| 文章编号： | 1002-8331-(2004)30-0049-02 |
A New Algorithm for Finding Kth Shortest Path |
| |
| Wang Mingzhong,Xie Jianying,Chen Yinglin.A New Algorithm for Finding Kth Shortest Path[J].Computer Engineering and Applications,2004,40(30):49-50,89. |
| |
| Authors: | Wang Mingzhong Xie Jianying Chen Yinglin |
| |
| Abstract: | We describe a new algorithm to figure out the Kth shortest simple(loopless)path in a undirected graph and report on its implementation.Our algorithm is based on 2nd shortest path algorithm and ″deviation path″.By K-1 times iteration of 2nd shortest path algorithm,we can finally find the Kth shortest path between two nodes assigned conveniently and quickly. |
| |
| Keywords: | Kth Shortest Path shortest path deviation path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
