DOI: 10.5176/2251-1938_ORS58
Authors: Liang Zhao and Mingji Gao
Abstract:
Given a directed or undirected graph 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 or to determine the non-existence of an s,d-path. For this problem, A* is a popular framework of practical algorithms, which includes the well-known Dijkstra’s algorithm (Dijkstra, 1959), a recent ALT algorithm (Goldberg and Harrelson, SODA ’05) and many others. This paper presents a practical speed-up technique Node Early-Fixing for A* algorithms. It generalizes a previous study Smart Update proposed by Zhao, Eumthurapojn and Nagamochi (AAAC 2011). Experiments on a number of real networks show that Node Early-Fixing can efficiently reduce the number of unnecessary updates for distance labels in practice.
Keywords: shortest path problem, point-to-point shortest path problem, A* algorithm
Updating...