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

Keywords

Path, Ranking, Deletion Path Algorithms

Journal

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