IBAS: Index Based A-Star

Abstract

The A-star algorithm is an efficient classical algorithm for solving the shortest path problem. The efficiency of the algorithm depends on the evaluation function, which is used to estimate the heuristic value of the shortest path from the current vertex to the target. When the vertex coordinates are known, the heuristic value of the shortest path is usually generated by the distance. In this paper, we present an Index Based A-Star algorithm (IBAS), which aims to solve the shortest path problem in a weighted directed acyclic graph with unknown vertex coordinates. This paper constructs three indexes for each vertex, i.e., the earliest arrival index, reverse earliest arrival index, and latest arrival index. We can compute the lower bound and the upper bound of the shortest distance from the source vertex to the target based on the three indexes and prune the intermediate vertices which are not in shortest path according to the lower and upper bounds. The IBAS algorithm not only makes use of the earliest arrival index to construct the evaluation function of the A-star algorithm but also utilizes the three indexes to prune useless vertices, so as to improve the performance of the algorithm. Compared with the A-star algorithm, the additional time complexity and space complexity of the IBAS algorithm are O(IV I + IEI) and O(IV I), respectively. A real road network and benchmark datasets with large-scale network are selected to verify the performance of IBAS. Experimental results verify the effectiveness of the proposed algorithm.

Keywords

• Shortest path
• A-star algorithm
• pruning strategy
• index