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

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 nearlinear-time algorithm for the problem that can also handle negative edge-weights; the runtime is O(m log8(n) log W). In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight single-source shortest paths to break through the classic O(m n log W) bound from more than three decades ago (Gabow and Tarjan SICOMP'89). We consider the single-source shortest paths (SSSP) problem with (possibly negative) integer weights. Given an m-edge n-vertex directed weighted graph G (V,E,w) with integral edge weight w(e) for every edge e E and a source vertex s V, the goal is to compute a shortest path from s. Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra's algorithm.