Sharing information for the all pairs shortest path problem

We improve the time complexity of the all pairs shortest path (APSP) problem for special classes of directed graphs. One is a nearly acyclic directed graph and the other is a directed graph with limited edge costs. The common idea for speed-up is information sharing by n single source shortest path (SSSP) problems that are solved for APSP. We measure the degree of acyclicity by the size, r, of a given set of feedback vertices. If r is small, the given graph can be considered to be nearly acyclic. We consider this parameter, r, in addition to the traditional parameters of the number of vertices, n, and that of edges, m  . In the first part we improve the existing time complexity of O(mn+r3)O(mn+r3) for the all pairs shortest path problem to O(mn+rnlogn). This complexity is equal to or better than the previous one for all values of r   under a reasonable assumption of m⩾nm⩾n. In the second part, we deal with a directed graph with non-negative integer edge costs bounded by c  . We show the all pairs shortest path (APSP) problem can be solved in O(mn+n2log(c/n))O(mn+n2log(c/n)) time with the data structure of cascading bucket system. We use the traditional computational model such that comparison–addition operations on distance data and random access with O(logn) bits can be done in O(1)O(1) time. Also the graph is not separated, meaning m⩾n−1m⩾n−1.