Single-Source Shortest Paths with Negative Real Weights in Õ(mn 8/9 ) Time

This paper presents a randomized algorithm for single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input graph with n vertices and m edges, the algorithm completes in Õ( mn 8/9 ) time with high probability. For real-weighted graphs, this result constitutes the first asymptotic improvement over the classic O ( mn )-time algorithm variously attributed to Shimbel, Bellman, Ford, and Moore.

Authors

• Jeremy T. Fineman

Keywords

• randomized algorithms
• shortest paths