A new shortest paths ranking algorithm

Ranking shortest paths is a classical network problem consisting of the determination of the K shortest paths connecting a given initial–destination pair of nodes such that the distance of the k^th path that is determined is no greater than the distance of any j^th one, for some j > k. In this paper an algorithm for ranking paths is reviewed, with its complexity being improved in terms of the required memory space. This improvement allows the ranking of really larger problems in reasonably small execution times, as shown by the presented computational experiments. In fact, for randomly generated networks with 10000 nodes, the algorithm ranks more than half of a million of paths in a short CPU execution time. This performance can be very important because of the potential practical applications of the problem, namely as a subproblem of the constrained shortest path problem and of the multiobjective shortest path problem.