View source for Shortest Path with Bidirectional Search

=Internal=
* [[Shortest_Path_in_a_Graph#Shortest_Path_Algorithms|Shortest Path in a Graph]]
=Overview=
Bidirectional search can be used to find the shortest path between a source and a destination node. It operates by running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found the shortest path. This algorithm is faster than the [[Breadth-First_Search-based_Shortest_Path_Algorithm|classic breadth-first search based shortest path]].

For a justification, consider a graph where every node has at most k adjacent nodes, and the shortest path from node s to node t has length d. For the classic breadth-first search algorithm, we visit k nodes at step 1, k<sup>2</sup> nodes at step 2, etc. For a path with length d, we visit k + k<sup>2</sup> + ... + k<sup>d</sup>.

In case of bidirectional search, the searches collide after approximately d/2 levels, at mid point. The searches visit 2 (k + k<sup>2</sup> + ... + k<sup>d/2</sup>).