All Shortest Distances in Large Serial Networks

摘要

The paper describes an algorithm for finding the shortest distances between all pairs of nodes in certain large networks. For highly 'serial' networks, i.e., those containing a substantial number of nodes connected to exactly two other nodes, the procedure is considerably more efficient than the traditional cascade algorithm -- decomposition method. Empirical results are given of an application of the algorithm to a large (357 nodes) urban transportation network. (Author)