A Decomposition Algorithm for the Shortest-Route Problem

Abstract

There are a number of methods for finding the shortest routes between all pairs of points in a network; even with the aid of modern electronic computers; however, it is difficult to apply these methods to large networks, partly because such an application requires a large amount of computer time but especially because it requires a very large amount of fast-access storage, capacity. The decomposition algorithm presented here is designed to facilitate the analysis of such networks; the basic idea is to decompose the network into parts, apply one of the existing (matrix) methods to each part separately, and then to reunite the parts. In addition to reducing greatly the required amount of fast-access storage that is required, the algorithm generally appreciably reduces the required computer time, provided the network is not too small.