New Bounds on the Complexity of the Shortest Path Problem
Michael L. Fredman · SIAM Journal on Computing · 1976
It is shown that $O(N^{5/2} )$ comparisons and additions suffice to solve the all-pairs shortest path problem for directed graphs on N vertices with nonnegative edge weights. In conjunction with preprocessing, this result is exploited to produce an $o(N^3 )$ algorithm for solving the shortest path problem.