Authors: Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
Published: 2025-01-20
DOI: 10.1145/3631536
Source: Full article
In the single-source shortest paths problem, the goal is to compute the shortest path tree from a designated source vertex in a weighted, directed graph. We present the first near-linear time algorithm for the problem that can also handle negative edge-weights; the runtime is