Bidirectional Dijkstra

Plain Dijkstra explores outward from the start in every direction — like an expanding circle. If your target is far away, most of that circle is wasted effort heading the wrong way. Bidirectional Dijkstra runs two searches at once — one forward from the source, one backward from the target — and stops when they collide in the middle. Two small circles cover far less area than one big one.

The picture

Why it’s faster

Suppose the shortest path has length $L$ and the graph branches out roughly uniformly (each node has about $b$ neighbors). A single Dijkstra has to explore on the order of $b^{L}$ nodes to reach depth $L$. Two searches each only need to reach depth $L/2$, exploring about $b^{L/2}$ nodes each:

$$b^{L/2} + b^{L/2} = 2\,b^{L/2} \;\ll\; b^{L}$$

For a path of length 10 and branching factor 4, that’s the difference between exploring ${\sim}4^{10} \approx 10^6$ nodes and ${\sim}2 \cdot 4^{5} \approx 2000$. The speedup is why real routing engines use this (and heavier variants like Contraction Hierarchies built on top of it).

How it works

Run two Dijkstras with separate distance tables and priority queues:

• Forward search from $s$ over the normal graph, tracking $\operatorname{dist}_f$.
• Backward search from $t$ over the graph with every edge reversed, tracking $\operatorname{dist}_b$. (On an undirected graph, “reversed” is the same graph.)

Alternate between them — expand one node from each side per round. Track the best complete path seen so far:

BidirectionalDijkstra(graph, s, t):
    dist_f[s] ← 0 ;  dist_b[t] ← 0     # two distance tables, rest ∞
    pq_f ← {(0, s)} ;  pq_b ← {(0, t)}
    best ← ∞ ;  meet ← none

    while pq_f and pq_b are both non-empty:
        # ---- one step of the forward search ----
        u ← pq_f.pop_min(); settle u in forward
        for edge (u → v, w):
            relax v in forward
            if v is settled in backward:                  # frontiers touch
                if dist_f[u] + w + dist_b[v] < best:
                    best ← dist_f[u] + w + dist_b[v] ;  meet ← v

        # ---- symmetric step of the backward search ----
        (same, expanding pq_b over reversed edges)

        if top(pq_f) + top(pq_b) ≥ best:   # ---- stopping rule ----
            return best, reconstruct(meet)

The subtle part: when to stop

The tempting mistake is to stop the instant the two frontiers first touch. That’s wrong — the first meeting point does not always lie on the shortest path. A cheaper path can still close through a node that neither side has finalized yet.

The correct rule: keep a running best (the cheapest $\operatorname{dist}_f[x] + \operatorname{dist}_b[x]$ seen over any touched node $x$), and only stop when

$$\min(\text{pq}_f) + \min(\text{pq}_b) \;\ge\; \text{best}$$

At that point the two smallest tentative distances still on the queues can’t combine to beat best, so no undiscovered path can improve it. Then rebuild the path by joining the forward parent chain from meet back to $s$ with the backward parent chain from meet forward to $t$.

Complexity

Asymptotically it’s still $O((V+E)\log V)$ — the same worst case as Dijkstra (on a graph shaped so the frontiers barely shrink the work). The win is a large constant-factor reduction in nodes explored on typical graphs, which is what matters in practice. Memory roughly doubles: two distance tables, two queues.

When to use it

• Best for: single source-to-target queries on large graphs where you have no heuristic (no notion of geographic direction). If you do have a good distance estimate, A* is usually the better tool — and the two can even be combined.
• Requires being able to traverse edges backward from the target — fine for most graphs, but note it for streaming or implicitly-defined graphs where you can only step forward.
• Not worth it for single-source-to-all-nodes (there’s no single target to search back from) — use plain Dijkstra there.