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

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.