Shortcut in the Decomposition Algorithm for Shortest Paths in a Network
T. C. Hu, W. T. Torres · IBM Journal of Research and Development · 1969
The problem considered is that of finding the shortest path between the two nodes of every pair in a large n-node network. A decomposition algorithm is proposed for use when the number of arcs is less than n(n-1). The network is first decomposed into several overlapping subnetworks. Next, with each subnetwork treated separately, conditional shortest paths are obtained using triple operations. Finally, these conditional shortest paths are used to obtain the shortest paths between paired nodes in the original network by matrix mini-summation. This decomposition algorithm requires less computer storage and fewer arithmetic operations than other known algorithms.