An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths

Sanjeev Khanna, Junkai Song

We present a randomized algorithm for the single-source shortest paths (SSSP) problem on directed graphs with arbitrary real-valued edge weights that runs in $n^{2+o(1)}$ time with…