An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

Abstract

An algorithm is described that solves the all pairs shortest path problem for a nonnegatively weighted directed graph of n vertices in average time $O(n^2 \log n)$. The algorithm is a blend of two previous shortest path algorithms, those of Dantzig [Management Sci., 6 (1960), pp. 187–190] and Spira [SIAM J. Comput., 2 (1973), pp. 28–32]. Bloniarz [SIAM J. Comput., 12 (1983), pp. 588–600] categorised a class of random graphs called endpoint independent graphs; the new algorithm executes in the stated time on endpoint independent graphs and represents an asymptotic improvement over the $O(n^2 \log n\log ^ * n)$ algorithm given by Bloniarz for this class of random graphs.