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.
|Keywords||bidirectional search, road network search, shortest path|
|Publisher||Erasmus School of Economics|
|Series||Econometric Institute Research Papers|
|Journal||Report / Econometric Institute, Erasmus University Rotterdam|
Pijls, W.H.L.M, & Post, H. (2009). Yet another bidirectional algorithm for shortest paths (No. EI 2009-10). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–9). Erasmus School of Economics. Retrieved from http://hdl.handle.net/1765/16100