Seth Pettie (University of Texas, Austin):
A shortest path algorithm for real-weighted graphs
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 representing
the dependencies between shortest paths emanating from nearby vertices
and (2) a method for computing exact distances from approximate
distances.