A new implementation of Yen's ranking loopless paths algorithm

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. © 2003 Springer-Verlag Berlin/Heidelberg.