Technical Note—Reducing Space Requirements for Shortest Path Problems
Operations Research · 1982 · Volume 30 · Issue 5
Abstract
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.
Keywords
112 dynamic programming applications, 321 information systems management
Enable JavaScript for citation tools and additional paper interactions.