Finding shortest paths in large network systems

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.

REFERENCES

• 1: Edward P.F. Chan and Ning Zhang, Finding Shortest Paths in Large Network Systems, TR-01-15, Department of Computer Science, University of Waterloo, May 2001.(http://sdb.uwaterloo.ca)
• 2: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming: Series A and B, v.73 n.2, p.129-174, May 31, 1996 [doi>10.1007/BF02592101]
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: David Hutchinson, Anil Maheshwari, and Norbert Zeh, An External-Memory Data Structure for Shortest Path Queries, Proceedings of International Symposium on Algorithms and Computation, 1999.
• 5: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Effective graph clustering for path queries in digital map databases, Proceedings of the fifth international conference on Information and knowledge management, p.215-222, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238497]
• 6: Richard J. Lipton, and Robert Endre Tarjan, A separator Theorem for Planar Graphs, SIAM Journal Applied Mathematics, 36 (1979) pp. 177--189.
• 7: Ning Jing , Yun-Wu Huang , Elke A. Rundensteiner, Hierarchical optimization of optimal path finding for transportation applications, Proceedings of the fifth international conference on Information and knowledge management, p.261-268, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238550]
• 8: Ning Jing , Yun-Wu Huang , Elke A. Rundensteiner, Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.409-432, May 1998 [doi>10.1109/69.687976]
• 9: Shashi Shekhar , Andrew Fetterer , Bjajesh Goyal, Materialization Trade-Offs in Hierarchical Shortest Path Algorithms, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.94-111, July 15-18, 1997
• 10: N. Zeh, An External-Memory Data Structure for Shortest Path Queries, Diplomarbeit, Friedrich-Schiller-Universitit Jena, Nov,1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Performance