Takaoka, Tadao2015-10-132015-10-131997TR-COSC 03/97http://hdl.handle.net/10092/11154In this paper we give three sub-cubic 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 2 n) time with O(nμ [square root] plog 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 non-negative general costs (real numbers) in O(log 2 n) time with o(n 3 ) subcubic cost. Previously this cost was greater than O(n 3 ). Finally we improve with respect to M the complexity O((Mn) μ) of a sequential algorithm for a graph with edge costs up to M into O(M 1/3 n (6+w)/3 (log n) 2/3 (log log n) 1/3 ) in the APSD problem, where w = 2:376.enCopyright Tadao Takaokaall pairs shortest path problemparallel algorithmunit cost problemgeneral cost problemtwo-phase algorithmDiscussion / Working PapersField of Research::08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics