Faster single-source shortest paths with negative real weights via proper hop distance

The textbook algorithm for single-source shortest paths with real-valued edge weights runs in O(mn) time on a graph with m edges and n vertices. A recent breakthrough algorithm by Fineman [Fin24] takes Õ mn 8/9 randomized time. We present an Õ mn 4/5 randomized time algorithm building on ideas from [Fin24].