A new improvement for a K shortest paths algorithm



The K shortest paths problem is a well known network optimization problem where it is intended to rank the K shortest paths between an initial and a terminal node in a network. The first algorithm for solving this problem
appeared by the fifties and since then several other algorithms have been proposed. These algorithms can be divided into two classes: one based on the Optimality Principle and another based on the determination of a tree of shortest paths. Moreover, in the first of these classes there can be considered labeling algorithms and deletion path algorithms.

In this paper an improvement for a known deletion path algorithm is presented which results in the improvement of its running time complexity when the worst case analysis is considered, from O(Km) to O(Kn log n). Comparative computational experiments regarding the proposed improvement and its former version are also reported, allowing possible conclusions about the obtained performances when the average case is considered.


Path, Ranking, Deletion Path Algorithms


Investigação Operacional, Vol. 21, pp. 47-60, January 2001

Cited by

Year 2002 : 1 citations

 A level set method for multiobjective combinatorial optimization: Application to the quadratic assignment problem,
M. Ehrgott, T. Stephan, and D. Tenfelde-Podehl,
Report in Wirtschaftsmathematik 84, Fachbereich Mathematik,
Universität Kaiserslautern, 2002.