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: A new 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. 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: 2008-11-24
File-URL: https://repub.eur.nl/pub/13901/EI2008-25.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2008-25
Keywords: bidirectional search, road network search, shortest path
Handle: RePEc:ems:eureir:13901