Portal de Periódicos da CAPES

A new implementation of Yen?s ranking loopless paths algorithm

2003; Springer Science+Business Media; Volume: 1; Issue: 2 Linguagem: Inglês

10.1007/s10288-002-0010-2

1619-4500

ErnestoQ.V. Martins, Marta Pascoal,

Advanced Optical Network Technologies

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 ${\cal 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.