TY - JOUR
T1 - A class of label-correcting methods for the K shortest paths problem
AU - Lacagnina, Valerio
AU - Pecorella, Antonio
AU - Pecorella, Antonio
AU - Pecorella, null
AU - Lacagnina, Valerio
AU - Lacagnina, Valerio
AU - Guerriero, Francesca
AU - Guerriero, null
AU - Musmanno, Roberto
AU - Musmanno, null
PY - 2001
Y1 - 2001
N2 - 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 then the double sweep method of Shier (1979); 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.
AB - 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 then the double sweep method of Shier (1979); 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.
KW - K shortest paths problem
KW - label correcting methods
KW - K shortest paths problem
KW - label correcting methods
UR - http://hdl.handle.net/10447/51736
UR - http://www.jstor.org/stable/pdfplus/3088637.pdf
M3 - Article
VL - 49
SP - 423
EP - 429
JO - Operations Research
JF - Operations Research
SN - 0030-364X
ER -