Two-Levels Greedy: a generalization of Dijkstra's shortest path algorithm

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.