Efficient algorithms for the all pairs shortest path problem with limited edge costs
Tadao Takaoka · Computing: The Australasian Theory Symposium · 2012
In this paper we deal with a directed graph G = (V, E) with non-negative integer edge costs where the edge costs are bounded by c and |V| = n and m = |E|. We show the all pairs shortest path (APSP) problem can be solved in O(mn + n2 log(c/n))) time with the data structure of cascading bucket system. The idea for speed-up is to share a single priority queue among n single source shortest path (SSSP) problems that are solved for APSP. We use the traditional computational model such that comparison-addition operations on distance data and random access with O(log n) bits can be done in O(1) time. Also the graph is not separated, meaning m ≥ n. Our complexity is best for a relatively large bound on edge cost, c, such that c = o(n log n).