Shortest Path with Bidirectional Search

Internal

• 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 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² nodes at step 2, etc. For a path with length d, we visit k + k² + ... + k^d.

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