A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$

Abstract

We present an algorithm which determines the shortest distances between all pairs of points in a nonnegatively weighted directed graph in average time $O(n^2 \log n\log ^ * n)$. This algorithm, which uses a search strategy similar to Dantzig [Management Sci., 2 (1960), pp. 187–190; Linear Programming and Extensions, Princeton Univ. Press, 1963] and Spira [SIAM J. Comput., 2 (1973), pp. 28–32] executes in the stated time over quite general classes of probability distributions on such graphs.