On algorithms for finding the k shortest paths in a network
On algorithms for finding the k shortest paths in a network
复制标题
DOI：
10.1002/net.3230090303
复制
发表时间：
1979-09
期刊：
影响因子：
2.1
通讯作者：
D. Shier
中科院分区：
文献类型：
--
作者：
D. Shier
本文在一个统一的框架内提出了计算网络中k条最短路的几种新算法。这些算法利用已被证明是有效的解决最短路径问题的战略。此外，进行了计算研究，以评估不同的“弧处理”的顺序，这是每个算法的特点的影响。使用生成的中等规模网格、完整网络和随机网络类进行测试。两个特定的算法成为最有前途的那些评估。
This paper presents, within a unified framework, several new algorithms for computing k shortest paths in a network. These algorithms utilize strategies which have proved to be efficient in solving shortest path problems. In addition, a computational study was conducted to assess the effects of the different “arc processing” orders which are characteristic of each algorithm. Testing was performed using generated classes of moderately large grid, complete and random networks. Two particular algorithms emerge as the most promising among those evaluated.