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

Valerio Lacagnina, Antonio Pecorella, Antonio Pecorella, Pecorella, Valerio Lacagnina, Valerio Lacagnina, Francesca Guerriero, Guerriero, Roberto Musmanno, Musmanno

Risultato della ricerca: Articlepeer review

15 Citazioni (Scopus)

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 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.
Lingua originaleEnglish
pagine (da-a)423-429
Numero di pagine7
RivistaOperations Research
Volume49
Stato di pubblicazionePublished - 2001

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Entra nei temi di ricerca di 'A class of label-correcting methods for the K shortest paths problem'. Insieme formano una fingerprint unica.

Cita questo