A new all-pairs shortest path algorithm for real-weighted graphs
Seth Pettie

Abstract:
We present a new algorithm for the all-pairs shortest path problem on real-weighted graphs. Our algorithm improves on Dijkstra's classical shortest path algorithm -- the previous best -- and runs in time O(mn + n^2 log log n), where m and n are the number of edges and vertices, respectively.

The new ingredients in our algorithm are (1) a method for computing exact distances from approximate ones and (2) a method for representing the dependencies that exist among shortest paths emanating from nearby vertices.

Host: Guy Blelloch