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.

, ,
Erasmus School of Economics
Econometric Institute Research Papers
Report / Econometric Institute, Erasmus University Rotterdam
Erasmus School of Economics

Pijls, W., & Post, H. (2008). A new bidirectional algorithm for shortest paths (No. EI 2008-25). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–6). Retrieved from