h2. Bidirectional search

bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

bq. Find the shortest path between two nodes nodes in a large graph, for example the Facebook friendship graph.

!blog/meet-in-the-middle?12fig26.gif!

The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ nodes.

A better solution starts from both nodes and sees when the two search spaces meet.  This reduces the number of states explored to $O(p^k/2^)$.

A better solution starts from both nodes and sees when the two search frontiers meet.  This reduces the number of states explored to $O(p^k/2^)$.

The approach works well with both path finding problems on explicit graphs and with implicit state graphs like the ones you find in games.