An Optimal Route Finding on Road Networks Using A*, Dijkstra & Bidirectional Algorithms: A Brief Comparison

In road networks with time-dependent paths, computation of point-to-point shortest paths is of great practical importance. However, there are few papers that describe efficient algorithms. We implement our approach using lower bounds on arc costs, which can be used to reduce the number of nodes that have to be explored by the forward search: since the precise arrival time at the destination is unknown, we start the forward search from the destination node in order to reduce the number of nodes that have to be explored. In this paper, for their research methods, heuristic search communities generally use A* as the benchmark algorithm. Yet, many road network research papers utilize Bidirectional Dijkstra's algorithm as a baseline and build on Dijkstra's algorithm. An examination of A* and Bidirectional Dijkstra performance in road networks are conducted here in order to determine if a principled explanation exists for their differences. According to our analysis, Bidirectional Dijkstra performs well in this domain.