Bidirectional search explores simultaneously from the start toward the goal and from the goal toward the start, stopping when the frontiers meet. This combines forward and backward search to reduce exploration. section 3.2 section 3.4.3
For shortest paths, bidirectional Dijkstra’s search initializes forward and backward frontiers, alternates their expansion, tracks explored nodes, and joins routes when the searches collide. Splitting the depth roughly in half can substantially reduce space: two searches of depth d/2 require O(b^(d/2)) space rather than O(b^d). section 3.4.3
Toronto road-network comparison
A comparison of Dijkstra’s and bidirectional Dijkstra’s search illustrates forward exploration from opposite ends while exploring 50,841 nodes in the City of Toronto. section 3.4.3
Algorithm 3.5 Bidirectional Dijkstra's
Inputs: A graph, a source node, a destination node Output: Shortest path from source to destination in the graph Initialize frontier_f ← initialized with source Initialize frontier_b ← initialized with destination Initialize explored_f ← empty Initialize explored_b ← empty Initialize found ← False Initialize collide ← False Initialize altr_expand ← False While frontier_f is not empty and frontier_b is not empty and not collide and not found do If altr_expand then Set node ← frontier_f.pop() Add node to explored_f For child in node.expand() do If child in explored_f then continue If child is destination then Update route ← child.route() Update found ← True If child in explored_b then Update route ← child.route() + reverse(overlapped.route()) Update collide ← True Add child to frontier_f Update altr_expand ← not altr_expand Else Update node ← frontier_b.pop() Add node to explored_b For child in node.expand() do If child in explored_b then continue If child is origin then Update route ← child.route() Update found ← True If child in explored_f then Update route ← reverse(child.route()) + overlapped.route() Update collide ← True Add child to frontier_b Update altr_expand ← not altr_expand Return route
Use the algorithm listing to trace frontier initialization, alternating expansion, explored sets, collision detection, and route reconstruction. section 3.4.3
