A simplified algorithm for the all pairs shortest path problem with O(n~2 log n) expected time

摘要

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O(n~2 log n) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has so far established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is n?n/ logn. In this paper, we remove the concept of critical point, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis.