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 -