A new algorithm for shortest path problem in large-scale graph

作者：Xiao, Li^*; Chen, Lixue; Xiao, Jingzhong

来源：Applied Mathematics & Information Sciences, 2012, 6(3): 657-663.

• A* algorithm
• the shortest path
• single-source algorithm
• preprocessing

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.

• 出版日期2012-9
• 单位西南石油大学; 西南民族大学