|
|
 |
| |
|
|
|
A new algorithm for shortest path problem in large-scale graph |
|
|
|
PP: 657-663 |
|
|
|
Author(s) |
|
|
|
Li Xiao,
Lixue Chen,
Jingzhong Xiao,
|
|
|
|
Abstract |
|
|
| 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. |
|
|
|
|
|
|
|
