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.

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

Pijls, W., & Post, H. (2009). Yet another bidirectional algorithm for shortest paths (No. EI 2009-10). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–9). Retrieved from