All Pairs Shortest Paths for Graphs with Small Integer Length Edges
Zvi Galil, Oded Margalit · Journal of Computer and System Sciences · 1997
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).