Bidirectional Dijkstra

How bidirectional Dijkstra works

Run two simultaneous Dijkstras: one starting from the source s, one starting from the target t (the latter traversing edges in their reverse direction). Each maintains its own priority queue, its own distance table, and its own settled set. At every step, alternate: pop the smallest-distance node from each frontier, relax outgoing edges, repeat.

When a node has been settled by both directions, you've found a path through it: dist_forward[v] + dist_backward[v]. Track the minimum across all such "meeting" nodes — call it best_path. The trick is knowing when to stop: continue until the top of both queues, summed, is at least best_path. Only then is no improvement possible.

Why it visits fewer nodes

Visualize forward-only Dijkstra as growing a disk of radius d around the source — area proportional to d² in a 2D grid or roughly to d^k for a graph of branching factor b. Bidirectional grows two disks of radius d/2, total area roughly cut in half (or worse for higher branching factors). On real road networks where the search graph branches roughly like a cube, the speedup is closer to 2^k-1 — typically 2× to 5×.

The right way to terminate

A common bug is to stop the moment the two frontiers first touch (the first node settled by both directions). This is wrong! The first meeting node might not lie on the actual shortest path; a better meeting may still be reached through different edges.

Correct termination: each iteration, examine the top of both queues. Let μ = top_forward + top_backward. If μ ≥ best_path_so_far, halt — no shorter combined path can exist (because any further settled node has distance ≥ μ from at least one side).

Worked example — 8-node graph

Suppose source S sits at the left of a graph and target T at the right. The forward search settles, in order: S (0), A (3), B (5), C (8). The backward search settles: T (0), G (2), F (5), E (7). The first meeting is at node D (settled by forward at distance 6, by backward at distance 6) — total path S→A→D→F→T at distance 12. The algorithm checks: queue tops are C (8) forward, E (7) backward, sum 15 — not ≥ 12. It continues, settles a few more, then queue tops jointly exceed 12. Halt: path length 12 confirmed.

Cost comparison: forward-only Dijkstra on the same graph would have settled all 8 nodes (since T is far). Bidirectional settled 5 forward + 5 backward = 10 settle operations, but each over a shallower frontier. Wall-clock: ~50% faster on this small example; on a road network of 10⁶ nodes, the asymmetry is dramatic.

Cost in real terms

On a continent-scale road network (~50 million nodes, ~120 million edges), plain Dijkstra from New York to Los Angeles takes ~2 seconds and visits ~25 million nodes. Bidirectional Dijkstra finishes in ~0.6 seconds and visits ~7 million nodes — roughly 3.5× faster. Add a Contraction Hierarchy on top and per-query time drops below 1 ms — a 2000× speedup over plain Dijkstra. The CH is the multiplier; bidirectional is the foundation.

Bidirectional Dijkstra vs alternatives

	Dijkstra (1-way)	Bidirectional Dijkstra	A*	Contraction Hierarchies	ALT
Time (typical)	O((V+E) log V)	~0.5× Dijkstra	O(bd) — heuristic-dep.	~0.001× Dijkstra	~0.1× Dijkstra
Preprocessing	None	None	None (good heuristic needed)	Heavy: O(N log N)	Medium: landmark distances
Memory	O(V)	2× O(V)	O(V)	O(V + shortcuts)	O(V · #landmarks)
Needs reverse graph	No	Yes	No	Yes	No
Heuristic?	No	No	Yes	No (geometric ordering)	Yes (landmark inequality)
Multiple targets	Free (single-source)	Re-run per target	Re-run per target	Re-run per target	Re-run per target
Best for	Sparse, all distances	Single src–dst	With domain heuristic	Production routing	Production routing

JavaScript implementation

// MinHeap helpers: see /cs/heap.html
function biDijkstra(graph, reverseGraph, source, target) {
  if (source === target) return { distance: 0, path: [source] };

  const dF = new Map(), dB = new Map();
  const prevF = new Map(), prevB = new Map();
  for (const v of Object.keys(graph)) { dF.set(v, Infinity); dB.set(v, Infinity); }
  dF.set(source, 0); dB.set(target, 0);

  const queueF = new MinHeap(), queueB = new MinHeap();
  queueF.push([0, source]); queueB.push([0, target]);

  const settledF = new Set(), settledB = new Set();
  let best = Infinity, meet = null;

  function relax(u, dirGraph, dist, prev, queue, otherDist, otherSettled) {
    for (const [v, w] of dirGraph[u] || []) {
      const alt = dist.get(u) + w;
      if (alt < dist.get(v)) {
        dist.set(v, alt); prev.set(v, u); queue.push([alt, v]);
      }
      // Check for meeting
      if (otherSettled.has(v)) {
        const total = alt + otherDist.get(v);
        if (total < best) { best = total; meet = v; }
      }
    }
  }

  while (queueF.size() && queueB.size()) {
    // Stop condition
    const topF = queueF.peek()[0];
    const topB = queueB.peek()[0];
    if (topF + topB >= best) break;

    // Expand the smaller frontier
    if (topF <= topB) {
      const [d, u] = queueF.pop();
      if (d > dF.get(u)) continue;
      settledF.add(u);
      relax(u, graph, dF, prevF, queueF, dB, settledB);
    } else {
      const [d, u] = queueB.pop();
      if (d > dB.get(u)) continue;
      settledB.add(u);
      relax(u, reverseGraph, dB, prevB, queueB, dF, settledF);
    }
  }

  if (meet === null) return null;
  // Reconstruct path through `meet`
  const left = [], right = [];
  for (let n = meet; n !== undefined; n = prevF.get(n)) left.unshift(n);
  for (let n = prevB.get(meet); n !== undefined; n = prevB.get(n)) right.push(n);
  return { distance: best, path: left.concat(right) };
}

Python implementation

import heapq
from math import inf

def bi_dijkstra(graph, reverse_graph, source, target):
    if source == target: return 0, [source]
    dF = {v: inf for v in graph}; dB = {v: inf for v in graph}
    pF = {v: None for v in graph}; pB = {v: None for v in graph}
    dF[source] = 0; dB[target] = 0
    qF = [(0, source)]; qB = [(0, target)]
    settledF, settledB = set(), set()
    best = inf; meet = None

    def relax(u, dir_graph, dist, prev, queue, other_dist, other_settled):
        nonlocal best, meet
        for v, w in dir_graph.get(u, []):
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt; prev[v] = u; heapq.heappush(queue, (alt, v))
            if v in other_settled:
                total = alt + other_dist[v]
                if total < best: best = total; meet = v

    while qF and qB:
        if qF[0][0] + qB[0][0] >= best: break
        if qF[0][0] <= qB[0][0]:
            d, u = heapq.heappop(qF)
            if d > dF[u]: continue
            settledF.add(u); relax(u, graph, dF, pF, qF, dB, settledB)
        else:
            d, u = heapq.heappop(qB)
            if d > dB[u]: continue
            settledB.add(u); relax(u, reverse_graph, dB, pB, qB, dF, settledF)

    if meet is None: return None
    left = []
    n = meet
    while n is not None: left.append(n); n = pF[n]
    left.reverse()
    right = []
    n = pB[meet]
    while n is not None: right.append(n); n = pB[n]
    return best, left + right

Variants and extensions

• Bidirectional A*. Apply a goal-directed heuristic in each direction. Tricky: heuristics in opposite directions must be 'consistent' with each other for correctness — see Pohl (1971) and the more recent ALT (A* + Landmark + Triangle inequality) algorithm. ALT preprocesses distances to ~16 landmarks then uses the triangle inequality as a tight bidirectional heuristic.
• Contraction Hierarchies (CH). Precompute a node ordering by 'importance' and add shortcut edges so queries only need to traverse upward in the ordering. Combined with bidirectional Dijkstra restricted to upward edges, queries become essentially constant-time on planar road graphs. Built into OSRM and Valhalla.
• Hub Labels (HL). A more aggressive preprocessing where each node stores distances to its "hub set". Query reduces to set intersection. Faster than CH on continent-scale data but requires gigabytes of preprocessing storage.
• Customizable Contraction Hierarchies (CCH). Two-stage: a metric-independent preprocessing on graph topology, then a fast metric customization when edge weights change (e.g., traffic updates). Used in Google Maps' interior routing.
• Goal-directed search with stopping on multi-target. When multiple destinations are needed (1-to-many), forward Dijkstra is often better than launching N bidirectional runs.

Famous bidirectional-search problems

OSRM's car-routing pipeline

OSRM extracts a graph from OpenStreetMap, builds a Contraction Hierarchy in a few hours, and then answers point-to-point queries with bidirectional Dijkstra over only upward edges. On a continent (e.g., the U.S. road network with ~50 M nodes), a typical query touches ~3,000 nodes and finishes in well under 1 ms. The "bidirectional" half is what makes the CH work — without it the search would scan a much larger upward cone from the source alone.

Word ladder via bidirectional BFS

"Transform START into END one letter at a time, using only valid dictionary words." Standard BFS from START reaches every word at distance ≤ d. Bidirectional BFS searches simultaneously from both ends, halving the expansion. LeetCode 127 (Word Ladder) gets a 5–10× speedup over unidirectional BFS when the word list has ~10,000 entries and the ladder length is 5+.

Common bugs and edge cases

• Stopping at first meeting. The first node settled by both sides is rarely on the optimal path. Use the queue-top-sum ≥ best stopping rule.
• Forgetting the reverse graph. On directed graphs, the backward search must traverse reversed edges. Building only the forward adjacency list silently gives wrong answers.
• Updating best in the wrong place. The "best path so far" must be updated every time the relaxed neighbor is already settled by the opposite direction — not only when a node first becomes settled in your direction.
• Asymmetric edge weights. On undirected graphs the forward and reverse adjacency lists are identical; on directed asymmetric graphs they differ. Confusing the two breaks the symmetry argument.
• Negative edge weights. Just like plain Dijkstra, the greedy invariant fails with negative edges. Use Bellman-Ford from both ends or a different algorithm entirely.
• Source equals target. Handle the trivial case explicitly — return distance 0 and path [source]. Otherwise the empty-search loop produces meet = null and an apparent "no path" error.