The Extension of the Cascade Algorithm to Large Graphs

Large graphs for which the calculation of the shortest distances between all vertices is required often consist of several parts with limited interconnections. This paper shows how this characteristic may be used to reduce computer storage for a matrix type calculation, to reduce calculations] labour, and to provide results in a form which is particularly convenient if a subsequent assignment of commodity flow to shortest paths is needed. The technique presented here allows the partition to be arbitrary, save for a single, easily achieved, condition.