A new implementation of Yen's ranking loopless paths algorithm
A new implementation of Yen's ranking loopless paths algorithm
复制标题
DOI：
10.1007/s10288-002-0010-2
复制
发表时间：
2003-06-01
影响因子：
2
通讯作者：
Pascoal, Marta M. B.
中科院分区：
文献类型：
--
作者：
Martins, Ernesto Q. V.;Pascoal, Marta M. B.
Yen算法是一个经典的算法，用于对网络中一对节点之间的K条最短无环路径进行排序。本文给出了Yen算法的一个实现。当考虑最坏情况分析时，原始算法和该实现都呈现O（Kn（m + n log n））计算复杂度顺序。然而，计算实验的报告，允许得出结论，在实践中，这种新的实现优于其他两个，Perko的实现和一个简单的。
Yen's algorithm is a classical algorithm for ranking the K shortest loopless paths between a pair of nodes in a network. In this paper an implementation of Yen's algorithm is presented. Both the original algorithm and this implementation present O(Kn(m + n log n)) computational complexity order when considering a worst-case analysis. However, computational experiments are reported, which allow to conclude that in practice this new implementation outperforms two other, Perko's implementation and a straightforward one.