CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishThe shortest path problem on weighted directed graphs is one of the basic network optimization problems. Its importance is mainly due to its applications in various areas, such as communication and transportation. Here we are interested in the single-source case. In this note we present a natural generalization of Dijkstra’s algorithm to the case in which negative weight edges are allowed, but only outside of any cycle. The resulting algorithm turns out to have the same asymptotic complexity of Dijkstra’s algorithm and shows a linear behavior in the case of acyclic graphs. In fact, we will also see that our proposed algorithm compares very well in practice with the most efficient shortest path algorithms available, such as the ones due to Dial, Pape, Pallottino, Glover et. al., and to Goldberg and Radzik.
| Titolo: | Two-Levels Greedy: a generalization of Dijkstra's shortest path algorithm |
| Autori interni: | |
| Data di pubblicazione: | 2004 |
| Rivista: | |
| Handle: | http://hdl.handle.net/20.500.11769/8301 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
Copyright © 2020