Search from the start AND the goal at the same time, meeting in the middle.
run two BFS frontiers (from start, from goal); stop when they intersect
Frequently asked questions
How is this like starting a phone-tree from both ends?
Imagine two friends starting a class phone-tree from opposite ends of the list to find a common contact faster - they meet in the middle in roughly half the time. Bidirectional search runs two searches at once, one forward from the start and one backward from the goal, and stops when they meet. Because each side only travels about half the distance, and search effort grows explosively with distance, meeting in the middle explores dramatically fewer nodes than one search going the whole way.
Why is searching from both ends faster than searching from one?
Search effort grows explosively with distance: if each node has b neighbours, reaching depth d explores about b^d nodes. Two searches that each only go to depth d/2 explore about b^(d/2) nodes each - and b^(d/2) + b^(d/2) is dramatically smaller than b^d. For example, with b=10 and d=6, one search touches a million nodes, while two half-depth searches touch about two thousand combined. Meeting in the middle turns one deep, wide search into two shallow ones.
How does bidirectional search know when the two sides have met?
Each search keeps its own visited set. After expanding a frontier, the algorithm checks whether any node now appears in both visited sets - the forward search's and the backward search's. The first such shared node is the meeting point. The full path is then built by joining the forward path from the start to that node with the backward path from that node to the goal. Detecting this intersection efficiently (usually with a hash set) is the key implementation detail.
What does bidirectional search require that plain BFS does not?
Two things. First, you must know the goal in advance - you cannot search backward from a goal you have not specified, unlike BFS which can explore outward to find any reachable target. Second, you must be able to traverse edges backward (find a node's predecessors), which is trivial in undirected graphs but needs reverse edges in directed ones. When both conditions hold and the graph is large, the speed-up is substantial.
How does bidirectional search relate to Dijkstra and A*?
The meet-in-the-middle idea is not limited to BFS. Bidirectional Dijkstra and bidirectional A* apply the same two-frontier trick to weighted graphs and heuristic search, and they are used in industrial route planners to find driving directions across entire road networks quickly. The termination condition becomes subtler with weights (you cannot stop at the very first shared node; you must account for path costs), but the core saving - two half-searches instead of one full one - carries over.
Where is bidirectional search used in practice?
Route planning is the headline use: finding a path across a huge road or transit network is far faster searching from both origin and destination. It appears in network routing, in social-graph queries (shortest connection between two people), and in puzzle solving where the goal state is known (like solving a Rubik's Cube, where you can search forward from the scramble and backward from the solved state). Anywhere both endpoints are known and the graph is large, it is a powerful optimisation.