Subcubic Cost Algorithms for the All Pairs Shortest Path Problem

Abstract.

In this paper we give three subcubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log ² n) time with $O(n^\mu/\sqrt{\log n})$ processors where μ = 2.688 on an EREW PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with nonnegative general costs (real numbers) in O(log ² n) time with o(n ³ ) subcubic cost. Previously this cost was greater than O(n ³ ) . Finally we improve with respect to M the complexity O((Mn) ^μ ) of a sequential algorithm for a graph with edge costs up to M to O(M ^1/3 n ^(6+ω)/3 (log n) ^2/3 (log log n) ^1/3 ) in the APSD problem, where ω = 2.376 .