AN ALL PAIRS SHORTEST-PATH ALGORITHM WITH EXPECTED TIME O(N2LOGN)
A MOFFAT, T TAKAOKA
SIAM Journal on Computing | SIAM PUBLICATIONS | Published : 1987
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 G. B. Dantzig and P. M. Spira. P. A. Bloniarz categorized 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.