Shortest Path with Bidirectional Search

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

Internal

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

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