On the comparison-addition complexity of all-pairs shortest paths

Abstract. We present an all-pairs shortest path algorithm for arbi-trary graphs that performs O(mn log ) comparison and addition op-erations, 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 Dijk-stra'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 eÆcient implementation.