Optimization Research for Bi-directional Dijkstra Algorithm of Spatial Analyses
Zhou Jun-hui · Journal of Hunan University of Arts and Science · 2007
The shortest path dijkstra algorithm is one of the functions of spatial analyses, traditional Dijkstra algorithm, its time complex degree is as much as direct ratio to square of vertex number in graph, hard to meet practical count requirement under too many vertex condition. On the basis of analyzing current Bi-directional algorithm Dijkstra, this paper proposes an improved Bi-directional Dijkstra algorithm using intermediate list acceleration by adjusting seek strategy, to ensure forward and backward seek to meet in center, notably cutting down running time. To be tested, the running efficiency of this algorithm improves 90% on average than traditional Dijkstra algorithm.