Shortcutting for Negative-Weight Shortest Path

George Z. Li, Jason Li, Satish Rao +1

Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in $O(n^{2.5}{\log }^{4.5}n)$ time, improving on prior work…