All Pairs Shortest Distances for Graphs with Small Integer Length Edges

AbstractThere is a way to transform the All Pairs Shortest Distances (APSD) problem where the edge lengths are integers with small (⩽M) absolute value into a problem with edge lengths in {−1,0,1}. This transformation allows us to use the algorithms we developed earlier ([1]) and yields quite efficient algorithms. In this paper we give new improved algorithms for these problems. 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 APSD(n,M) algorithm which runs inO(T(n,M)) time, where[formula]2. A undirected APSD(n,M) algorithm which runs inO(M(ω+1)/2nωlog(Mn)) time