Abstract
For the first time, this paper proposes the Network-Tree Model (NTM), route optimization theory and wholly new, high performance algorithm for shortest path calculation in large-scale network. We first decompose the network into a set of sub-networks by adopting the idea of multi-hierarchy partition and anomalistic regional partition, and then construct the NTM and the Expanded NTM. The Network-Tree Shortest Path (NTSP) algorithm presented in this paper narrows the searching space of the route optimization within a few sub-networks, so it greatly reduces the requirements for main memory and improves the computational efficiency compared to traditional algorithms. Experiment results based on grid network show that NTSP algorithm achieves much higher computational performance than Dijkstra algorithm and other hierarchical shortest path algorithms.
This work was supported in part by Grand 99025 of Ministry of Education and Grand 9810200104 of Liaoning Science Foundation, China.
Chapter PDF
Similar content being viewed by others
References
Cherkassky B.V., Goldberg A.V., Radzik T.: Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 1996, 73(2): 129–174
Ning Jing, Yun-Wu Wang, and 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, 1998, 10(3): 409–432
A. Car, G. Taylor, C. Brunsdon. An analysis of the performance of a hierarchical way finding computational model using synthetic graphs. Computers, Environment and Urban Systems, 2001, 25: 69–88
J. Shapiro, J. Waxman, D. Nir: Level Graphs and Approximate Shortest Path Algorithms, Networks, 1992, 22: 691–717
Yu-Li Chou, H. Edwin Romeijn and Robert L. Smith: Approximating Shortest Paths in Large-Scale Networks with an Application to Intelligent Transportation Systems, INFORMS journal on Computing, 1998, 10(2): 163–179
Chan-Kyoo Park, Kiseok Sung, Seungyong Doh, Soondal Park: Finding a path in the hierarchical road networks. 2001 IEEE Intelligent Transportation Systems Conference Proceedings-Oakland (CA) USA, August 25–29, 2001, pp. 936–942
A. Fetterer, S. Shekhar: A Performance Analysis of Hierarchical Shortest Path Algorithms. IEEE Proceedings of the International Conference on Tools with Artificial Intelligence, Nov 3–8, 1997, pp. 84–92
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tan, G., Han, X., Gao, W. (2003). Network-Tree Model and Shortest Path Algorithm. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J.J., Zomaya, A.Y. (eds) Computational Science — ICCS 2003. ICCS 2003. Lecture Notes in Computer Science, vol 2659. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44863-2_53
Download citation
DOI: https://doi.org/10.1007/3-540-44863-2_53
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40196-4
Online ISBN: 978-3-540-44863-1
eBook Packages: Springer Book Archive