A class of label-correcting methods for the K shortest paths problem

A class of label-correcting methods for the K shortest paths problem

0.00 Avg rating0 Votes
Article ID: iaor20021957
Country: United States
Volume: 49
Issue: 3
Start Page Number: 423
End Page Number: 429
Publication Date: May 2001
Journal: Operations Research
Authors: , , ,
Keywords: optimization
Abstract:

In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that: 1, some label-correcting methods are generally much faster than the double sweep method of Shier; 2, the most efficient node selection strategies, used for solving the classical single-origin all-destinations shortest path problem, have proved to be effective also in the case of the K shortest paths.

Reviews

Required fields are marked *. Your email address will not be published.