The 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.
Two-Levels Greedy: a generalization of Dijkstra's shortest path algorithm
CANTONE, Domenico;FARO, SIMONE
2004-01-01
Abstract
The 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.File | Dimensione | Formato | |
---|---|---|---|
Cantone-Faro-ENDM2004.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Dimensione
199.29 kB
Formato
Adobe PDF
|
199.29 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.