Node Early-Fixing: A Practical Speedup Technique for A* Algorithms

DOI: 10.5176/2251-3388_2.1.39

Authors: Liang Zhao and Mingji Gao

Abstract:
Given a graph G with nonnegative edge lengths, a source vertex s and a destination vertex d, the Point-to-Point Shortest Path Problem asks to find a shortest path from s to d. For this problem, A* is a popular framework of practical algorithms, including the well-known Dijkstra’s algorithm (1959), a recent ALT algorithm (Goldberg and Harrelson, SODA’05) and others. This paper presents a practical speed-up technique Node Early-Fixing for A* algorithms. Experiments with real networks show that it can speedup the calculation by efficiently reduce the number of unnecessary updates of distance labels in practice.

Keywords: shortest path problem, Dijkstra’s algorithm, A* algorithm, speedup technique