Zhang Ke-Hong
School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024, China
Li Ke-Qiu
School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024, China
ABSTRACT
The shortest path algorithm has developed for decades, there are Dijkstra algorithm, A* algorithm and Floyd-Warshall algorithm which are all less information and smaller size , so, they have certain limitations in the efficiency of processing large-scale graph data. This paper summarized this field from landmark, hierarchical technology, index and decomposition of the tree, the bidirectional search and the heuristic method etc, especially it emphasized on some latest and the most representative algorithms under the background of large-scale graph data.
PDF References
How to cite this article
Zhang Ke-Hong and Li Ke-Qiu, 2013. Survey of Rapidly Calculating the Shortest Path of Large-scale Graph. Information Technology Journal, 12: 3510-3516.
DOI: 10.3923/itj.2013.3510.3516
URL: https://scialert.net/abstract/?doi=itj.2013.3510.3516
DOI: 10.3923/itj.2013.3510.3516
URL: https://scialert.net/abstract/?doi=itj.2013.3510.3516
REFERENCES
- Blondel, V.D., J.L. Guillaume, R. Lambiotte and E. Lefebvre, 2008. Fast unfolding of communities in large networks. J. Stat. Mech.
CrossRef - Dijkstra, E.W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1: 269-271.
CrossRefDirect Link - Dorigo, M., V. Maniezzo and A. Colorni, 1996. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B: Cybern., 26: 29-41.
CrossRefDirect Link - Chan, E.P.F. and Y. Yang, 2009. Shortest path tree computation in dynamic graphs. IEEE Trans. Comput., 58: 541-557.
CrossRef - Wei, F., 2010. TEDI: Efficient shortest path query answering on graphs. Proceedings of the International Conference on Management of Data, June 6-11, 2010, Indianapolis, IN., USA., pp: 99-110.
CrossRef - Gao, W.Y. and S.H. Li, 2012. Tree decomposition and its applications in algorithms: Survey. Comput. Sci., 39: 14-18.
Direct Link - Gao, J., R.M. Jin, J.S. Zhou, J.X. Yu, X. Jiang and T. Wang, 2011. Relational approach for shortest path discovery over large graphs. Proc. VLDB Endowment, 5: 358-369.
Direct Link - Geisberger, R., P. Sanders, D. Schultes and D. Delling, 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Proceedings of the 7th International Workshop on Experimental Algorithms, May 30-June 1, 2008, Provincetown, MA., USA., pp: 319-333.
CrossRef - Gubichev, A., S. Bedathur, S. Seufert and G. Weikum, 2010. Fast and accurate estimation of shortest paths in large graphs. Proceedings of the 19th ACM International Conference on Information and Knowledge Management, October 26-30, 2010, Toronto, Ontario, Canada, pp: 499-508.
CrossRef - Jin, R.M., N. Ruan, Y. Xiang and V.E. Lee, 2012. A highway-centric labeling approach for answering distance queries on large sparse graphs. Proceedings of the ACM SIGMOD International Conference on Management of Data, May 20-24, 2012, Scottsdale, AZ., USA., pp: 445-456.
CrossRef - Potamias, M., F. Bonchi, C. Castillo and A. Gionis, 2009. Fast shortest path distance estimation in large networks. Proceedings of the 18th ACM Conference on Information and Knowledge Management, November 2-6, 2009, Hong Kong, China, pp: 867-876.
CrossRef - Rice, M. and V.J. Tsotras, 2010. Graph indexing of road networks for shortest path queries with label restrictions. Proc. VLDB Endowment, 4: 69-80.
Direct Link - Sarma, A.D., S. Gollapudi, M. Najork and R. Panigrahy, 2010. A sketch-based distance oracle for web-scale graphs. Proceedings of the 3rd ACM International Conference on Web Search and Data Mining, February 3-6, 2010, New York City, NY., USA., pp: 401-410.
CrossRef - Song, Q. and X. Wang, 2011. Efficient routing on large road networks using hierarchical communities. IEEE Trans. Intell. Transp. Syst., 12: 132-140.
CrossRef - Song, Q. and X.F. Wang, 2012. Survey of speedup techniques for shortest path algorithms. J. Univ. Electron. Sci. Technol. China, 41: 176-184.
Direct Link - Tretyakov, K., A. Armas-Cervantes, L. Garcia-Banuelos, J. Vilo and M. Dumas, 2011. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. Proceedings of the 20th ACM International Conference on Information and Knowledge Management, October 24-28, 2011, Glasgow, UK., pp: 1785-1794.
CrossRef - Virgilio, R.D., A. Maccioni and R. Torlone, 2013. A similarity measure for approximate querying over RDF data. Proceedings of the Joint EDBT/ICDT 2013 Workshops, March 18-22, 2013, Genoa, Italy, pp: 205-213.
CrossRef - Wang, Y. and Q.D. Ye, 2012. Improved strategies of ant colony algorithm for solving shortest path problem. Comput. Eng. Appl., 48: 35-38.
Direct Link - Yuan, Y., G.R. Wang, H.X. Wang and L. Chen, 2011. Efficient subgraph search over large uncertain graphs. Proc. VLDB Endowment, 4: 876-886.
Direct Link