Finding Shortest Paths in Large Network Systems Edward P. F. Chan and Ning Zhang   View Paper (PDF)   Return to Inelegant Transportation Systems and Network Algorithms Abstract This paper describes a disk-based algorithm for finding shortest paths in a large network system. It employs a strategy of processing the network piece by piece and is based on new algorithms for graph partitioning and for finding shortest paths that overcome the problem of existing approaches. To show that it is scalable to large network systems and is adaptable to different computing environments, seven states in Tiger/Line files are extracted as test cases and are experimented on machines with different configurations. The running time for finding the shortest path depends primarily on the power of the underlying systems. Moreover, to run the algorithm optimally, the memory requirement is not large, even for a very large network system such as the road system in several states in Tiger/Line file. To evaluate its performance, New Mexico state road system is used as the test case, and is compared with Dijkstra's algorithm. The average running time of the proposed algorithm is, in the worst case, about two and a half times slower than that of Dijkstra's algorithm; provided that in Dijkstra's algorithm, the whole graph can be fit into main memory and is already loaded in advance. If the I/O time for loading the whole graph is counted, the proposed algorithm is faster in essentially all cases. DiSC'02 © 2003 Association for Computing Machinery