Archivio istituzionale della ricerca dell'Università degli Studi di Palermo
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, pubblicazioni, progetti, attività) adottato dall’Università di Palermo, e ha lo scopo di raccogliere, conservare, documentare, e diffondere ad accesso aperto le informazioni relative alla produzione scientifica degli autori afferenti all’Ateneo.
EnglishIn 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.
Guerriero, F., Musmanno, R., Lacagnina, V., & Pecorella, A. (2001). A class of label-correcting methods for the K shortest paths problem. OPERATIONS RESEARCH, 49(3), 423-429 [10.1287/opre.49.3.423.11217].
| Data di pubblicazione: | 2001 | |
| Titolo: | A class of label-correcting methods for the K shortest paths problem | |
| Autori: | ||
| Citazione: | Guerriero, F., Musmanno, R., Lacagnina, V., & Pecorella, A. (2001). A class of label-correcting methods for the K shortest paths problem. OPERATIONS RESEARCH, 49(3), 423-429 [10.1287/opre.49.3.423.11217]. | |
| Rivista: | ||
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1287/opre.49.3.423.11217 | |
| URL: | http://www.jstor.org/stable/pdfplus/3088637.pdf | |
| Settore Scientifico Disciplinare: | Settore SECS-S/06 -Metodi Mat. dell'Economia e d. Scienze Attuariali e Finanz. | |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| 2001_A Class Of Label Correcting Methods for the K Shortest Paths Problem.pdf | articolo completo | N/A | Administrator Richiedi una copia |
http://hdl.handle.net/10447/51736
Copyright © 2022