The shortest path problem is one of the basic problems in graph theory, which attracted a lot of attention of many scholars. However, with the continuous development of intelligent transportation, communications systems, many complex network structures with large-scale nature occurred, which have a larger amount of data and algorithm execution efficiency requirement, compared with the traditional shortest path problems. It first research and analyze the traditional serial A * algorithm in this article, the defect of the A * algorithm is proposed to improve. The optimization algorithm opposed in this article is named single-source algorithm. The new algorithm have lower time-complexity and more efficient processing in large-scale map compared with the A * algorithm, which take into account a variety of methods, including data preprocessing, improving the search ways, as well as the evaluation function and the internal data structure. The conclusion of the study is verified by simulation.
Xiao, Li; Chen, Lixue; and Xiao, Jingzhong
"A new algorithm for shortest path problem in large-scale graph,"
Applied Mathematics & Information Sciences: Vol. 06
, Article 36.
Available at: https://dc.naturalspublishing.com/amis/vol06/iss3/36