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.
2004
Shortest-Path Problem, Dijkstra's Algorithm, Graphs Algorithms
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/8301
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? ND
social impact