CoreSource checked

Bidirectional Dijkstra

Finds a shortest path by running Dijkstra search forward from the start and backward from the goal.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Intermediate
Family: Shortest Path
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 2
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

Bidirectional Dijkstra shrinks the explored area when both directions use compatible edge costs and stop after the best meeting path is proven optimal.

Core Concepts

two-frontier searchpriority queuedistance relaxationmeeting condition

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E log V)

Average

O(E log V)

Worst

O(E log V)

Space

O(V)

When to Use

Use when route planning needs two-frontier search.
Use when the input matches the assumptions behind shortest Path.

When Not to Use

Avoid when edge costs or movement rules change faster than the search can update them.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Finds a shortest path by running Dijkstra search forward from the start and backward from the goal
Uses two-frontier search and priority queue to guide the work.
Produces path.

Use Cases

Route planning
Game navigation
Robotics motion planning

Inputs

Search graph or state space
Start state
Goal state or target set

Outputs

Path
Distance estimate
Search frontier state

Key Formulas (2)

Relaxation step

dist_[v] = min(dist_[v], dist_[u] + weight(u, v))

dist[v] = min(dist[v], dist[u] + weight(u, v))

Updates a candidate distance when a route through the current node is shorter.

Best path through meeting node

best = min(best, dist_f_[v] + dist_b_[v])

best = min(best, dist_f[v] + dist_b[v])

Tracks the shortest path found where the two searches meet.

Pseudocode

1.Prepare the inputs and state needed for Bidirectional Dijkstra.
2.Apply the two-frontier search step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return path.

Canonical Example

Input: road graph with start S and target T
Output: shortest S-to-T path after forward and reverse searches meet
Explanation: The two Dijkstra frontiers expand from opposite ends and stop when their settled distances prove no shorter joining path remains.

Implementation Notes

Maintain separate forward and reverse distance maps.
Update the best known connecting path whenever a node is reached from both directions.
Stop only when the priority-queue minima cannot improve the best connection.

Common Pitfalls

Stopping at the first meeting point instead of using a correct termination bound.
Using a reverse search without correctly reversing directed edges.
Combining distances from unsettled nodes as if they were final.