Abstract: It is well known that any algorithm to compute the shortest path between any two vertices in a graph must take the same asymptotic time as an algorithm that computers a single-source all-destinations tree. But space complexity is another matter. The authors develop an algorithm paradigm for reporting an optimal path between two vertices without growing an entire single-source all-destinations tree. This brings forth a new technique, prune and search, and a new data structure, the clipped tree. These are used to improve the space bounds on previously best known algorithms.
This paper appeared in Journal of Algorithms 49:1 (October 2003), pp. 13-41.