Meeting in the middle
Bidirectional search runs two searches simultaneously: one expanding outward from the start, the other expanding backward from the goal along reversed edges. When the two frontiers touch, a path has been found.
Why it helps
A single search explores a frontier that grows with depth. Two shallower searches each explore far fewer nodes, because the explored region of each one only needs to reach the midpoint rather than the full distance.
- Forward frontier grows from the start.
- Backward frontier grows from the goal.
- Stop when a node appears in both frontiers.
The subtle part is the stopping rule. For weighted graphs you cannot stop at the very first touch; you must continue until no cheaper meeting point can exist.
Key idea
Bidirectional search grows frontiers from both ends and stops when they meet, dramatically shrinking the explored region compared with searching from one side alone.