# A new improvement for a K shortest paths algorithm

### Authors

### Abstract

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 problemappeared 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.

### Keywords

Path, Ranking, Deletion Path Algorithms### Journal

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.