Negative-Weight Single-Source Shortest Paths in Near-Linear Time.

In this research article, the authors present a simple combinatorial algorithm that reduces running time to near-linear to address the single-source shortest paths problem. The authors present two questions-- including can the algorithm perform without complex machinery-- and five theorems--that deal with negative-weight cycle-- in this research and evaluate two algorithms, ScaleDown and the simpler SPMain, in regards to these. Topics include price functions and low-diameter decomposition.