1. Node Early-Fixing: A Practical Speedup Technique for A* Algorithms.
- Author
-
Liang Zhao and Mingji Gao
- Subjects
- *
COMPUTER algorithms , *GRAPH theory , *NONNEGATIVE matrices , *PATH analysis (Statistics) , *COMPUTER network architectures - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF