Finding the hidden path: time bounds for all-pairs shortest paths

The all-pairs shortest paths problem in weighted graphs is investigated. An algorithm called the hidden paths algorithm, which finds these paths in time O(m*+n n/sup 2/ log n), where m* is the number of edges participating in shortest paths, is presented. It is argued that m* is likely to be small in practice, since m*=O(n log n) with high probability for many probability distributions on edge weights. An Omega (mn) lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest paths problem is proved.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>