Template-Type: ReDIF-Paper 1.0
Author-Name: Pijls, W.H.L.M.
Author-Name-Last: Pijls
Author-Name-First: Wim
Author-Name: Post, H.
Author-Name-Last: Post
Author-Name-First: Henk
Title: Yet another bidirectional algorithm for shortest paths
Abstract: For finding a  shortest path in a network the bidirectional~A* algorithm is a widely known algorithm.                       An A* instance requires a heuristic estimate, a real-valued function on the set of nodes.                                   %This algorithm distinguishes  between the main phase and the postprocessing phase.                                         %As long as  the search processes of the two sides do not meet, we are in the main phase.                                   %As soon as a meeting point is obtained, the post-phase is in progress. \\\\                                                  The version of bidirectional~A* that is considered the most appropriate in literature hitherto,                             uses  so-called balanced heuristic estimates.                                                                               This means that the two estimates of the two directions are in balance, i.e., their sum is a constant value.                In this paper, we do not restrict ourselves any longer to balanced heuristics.                                              A generalized version of bidirectional A* is proposed, where the heuristic estimate does not need to be balanced.           This new version turns out to be faster than the one with the balanced heuristic.
Creation-Date: 2009-06-16
File-URL: https://repub.eur.nl/pub/16100/ei2009-10.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2009-10
Keywords: bidirectional search, road network search, shortest path
Handle: RePEc:ems:eureir:16100