We present an all-pairs shortest path algorithm for arbitrary graphs that performs O(mn log α) comparison and addition operations, where m and n are the number of edges and vertices, resp., and α = α(m, n) is Tarjan's inverse-Ackermann function. Our algorithm eliminates the sorting bottleneck inherent in approaches based on Dijkstra's algorithm, and for graphs with O(n) edges our algorithm is within a tiny O(log α) factor of optimal. The algorithm can be implemented to run in polynomial time (though it is not a pleasing polynomial). We leave open the problem of providing an efficient implementation.
展开▼
