Yet another bidirectional algorithm for shortest paths

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.