A new implementation of Yen's ranking loopless paths algorithm

Authors

Marta Margarida Braz Pascoal
E. Q. V. Martins

Abstract

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.

Keywords

Network, Path, Loopless Path, Paths Ranking

Journal

4OR -- Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Vol. 1, #2, pp. 121-134, January 2003

Cited by

Year 2005 : 3 citations

Finding the K Shortest Hyperpaths,
L.R. Nielsen and K.A. Andersen and D. Pretolani,
Computers & Operations Research, 32, (6), 1477-1497 (2005).

Modified distributed relative capacity loss algorithm for WDM optical networks,
R. G. Dante, E. Moschim, and J. F. Martins-Filho,
J. Opt. Netw. 4, 271-284 (2005).

Effective Failure Recovery Schemes for Survivable Networks,
Dahai Xu,
Ph.D. thesis, Department of Computer Science and Engineering, State University of New York at Buffalo (2005).

Year 2004 : 1 citations

Route Choice in Stochastic Time-Dependent Networks,
L.R. Nielsen,
Ph.D. thesis, Department of Operations Research, University of Aarhus (2004).

Year 2003 : 3 citations

On the Difficulty of Some Shortest Path Problems,
A. M. Bhosle,
M.Sc. thesis, Department of Computer Science, University of California (2002).

On the Difficulty of Some Shortest Path Problems,
J. Hershberger , S. Suri, A. M. Bhosle,
STACS '03: 20th International Symposium on Theoretical Aspects of Computer Science, 27 Feb - 01 March 2003, Berlin, Germany.

Trap Avoidance and Protection Schemes in Networks with Shared Risk Link Groups,
D. Xu, Y. Xiong, C. Qiao, G. Li,
IEEE Journal of Lightwave Technology, Vol. 21, No. 11, Nov. 2003, pp 2683-2693.