Bidirectional Dijkstra's Algorithm
What you'll learn: How running Dijkstra's algorithm simultaneously from both source and target can dramatically speed up shortest path queries.
The Core Idea
Instead of searching outward from just the source node until you reach the target, bidirectional Dijkstra's launches two simultaneous searches: one forward from the source and one backward from the target. The algorithm terminates when these two "wavefronts" meet in the middle.
Think of it like two people searching for each other in a crowded mall. If both start walking toward the center, they'll meet much faster than if one person stays put while the other searches the entire building.
How It Works
Each search maintains its own priority queue and visited set:
- Forward search relaxes edges normally (source → neighbors)
- Backward search relaxes edges in reverse (target ← predecessors)
The algorithm stops when a node is visited by both searches. At this point, you've found a shortest path that goes: source → meeting point → target.
Why It's Faster
In standard Dijkstra's, you might explore a huge portion of the graph before reaching the target. With bidirectional search, each direction only needs to explore roughly half the distance, which can reduce the search space from O(n) to O(√n) in many practical graphs—especially road networks or grids where distance matters.
This is especially powerful when combined with early termination techniques you've already learned.
Key Takeaway: Bidirectional Dijkstra's runs two simultaneous searches from source and target, meeting in the middle to potentially cut search space and runtime roughly in half compared to standard Dijkstra's algorithm.