A class of label-correcting methods for the K shortest paths problem
成果类型：
Article
署名作者：
Guerriero, F; Musmanno, R; Lacagnina, V; Pecorella, A
署名单位：
University of Calabria; University of Salento; University of Palermo
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.3.423.11217
发表日期：
2001
页码：
423-429
关键词：
摘要：
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 (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.