A new approach to all-pairs shortest paths on real-weighted graphs

✍ Scribed by Seth Pettie

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 380 KB
• Volume: 312
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00402-x

✦ Synopsis

We present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. It runs in O(mn + n 2 log log n) time, improving on the long-standing bound of O(mn + n 2 log n) derived from an implementation of Dijkstra's algorithm with Fibonacci heaps. Here m and n are the number of edges and vertices, respectively.

Our algorithm is rooted in the so-called component hierarchy approach to shortest paths invented by Thorup for integer-weighted undirected graphs, and generalized by Hagerup to integer-weighted directed graphs. The technical contributions of this paper include a method for approximating shortest path distances and a method for leveraging approximate distances in the computation of exact ones. We also provide a simple, one line characterization of the class of hierarchy-type shortest path algorithms. This characterization leads to some pessimistic lower bounds on computing single-source shortest paths with a hierarchy-type algorithm.