Shortest Route Algorithms for Sparsely Connected Networks.

摘要

This report studies the shortest route problem for networks that are less fully connected. Two algorithms are presented which exploit the absence of arcs in solving the shortest route problem. The first, which is designated the NXN algorithm, would tend to be the more applicable to networks typically encountered in practice. The second, which is an improvement on Hu's decomposition shortest route algorithm, is more efficient for a small class of networks; however, it generally requires less memory to hold the required decomposition information in the computer than does the NXN algorithm. (Author)