All Pairs Shortest Paths for Graphs with Small Integer Length Edges

Abstract

The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (⩽M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number of vertices,Mthe bound on edge length, andωthe exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSP(n, M) algorithm which runs inÕ(T(n, M)) time, where T(n, m)=\big\{\begin{align}M^{\omega -1)/2} n^{3+\omega )/2}, & 1\le M\le n^{3-\omega )/(\omega +1)}\\ Mn^{5\omega -3)/(\omega +1)}, & n^{(3-\omega )/(\omega +1)}\le M\le n^2(3-\omega )/(\omega +1)}.\end{align} 2. An undirected APSP(n, M) algorithm which runs inÕ(M(ω+1)/2nω log(Mn)) time. 3. A general APSP(n, M) algorithm which runs inÕ((Mn)(3+ω)/2).