This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Guerriero, F. Articles by Pecorella, A. Search for Related Content

A Class of Label-Correcting Methods for the K Shortest Paths Problem

Università degli Studi della Calabria, Rende, Italy
Università degli Studi di Lecce, Lecce, Italy, roberto
Università degli Studi di Palermo, Palermo, Italy
Università degli Studi di Palermo, Palermo
guerrier{at}parcolab.unical.it
roberto.musmanno{at}unile.it
ricopa{at}unipa.it
tonpec{at}unipa.it

In this paper we deal with the problem of finding the first Kshortest 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 Klists 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 Kshortest paths.

Subject classifications: Network/Graphs: algorithms for the K shortest paths problem.
History: Received March 1998; revision received November 1999; accepted January 2000.