Technical Note—Reducing Space Requirements for Shortest Path Problems

The problem of determining the shortest path through a level network using as little space as possible is considered. Let k denote the number of levels and assume each level contains m nodes. A space efficient technique is presented by which the shortest route from a source to a sink may be found in a complete level graph using θ(m + k) storage locations and a factor of only θ(log k) more basic operations than space inefficient methods. If an edge from node p of level i to node q of level i + 1 exists only if p ≥ q, then the space saving technique may also be employed. In this case the run time of the algorithm is at most twice that of conventional approaches.