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

  • Liang Zhao
  • 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.

Published
2018-05-11
How to Cite
ZHAO, Liang; GAO, Mingji. Node Early-Fixing: A Practical Speedup Technique for A* Algorithms. GSTF Journal of Mathematics, Statistics and Operations Research (JMSOR), [S.l.], v. 2, n. 1, may 2018. ISSN 2251-3396. Available at: <http://dl6.globalstf.org/index.php/jmsor/article/view/1537>. Date accessed: 19 dec. 2018.