The cost of a Dijkstra search grows with the area it settles, and that area grows with the square of the distance searched. Expanding from both ends turns one large disc into two small ones, which on a long route is a substantial saving for very little code. This page covers doing it correctly on a directed graph, as part of NetworkX shortest-path algorithms for logistics within Python Routing Engines & Isochrone Mapping.

The saving is easy to get. Correctness is the part people get wrong, and the wrong version returns a path that is very nearly shortest, which is the hardest kind of bug to notice.

When to use this approach

Bidirectional search pays when the route is long relative to the graph’s density, which in practice means inter-city and regional freight legs rather than urban delivery hops. It is also the natural default when no admissible heuristic is available, since it delivers a comparable saving to A* without needing coordinates.

It does not help, and should not be used, for isochrone or service-area work. Those are single-source bounded expansions with no target, so there is nothing to search backward from — a distinction covered in generating isochrones with PySAL and GeoPandas.

One large disc against two small ones A unidirectional search settles a disc of radius equal to the route length. A bidirectional search settles two discs of half that radius, and because area grows with the square of radius the two together cover about half the nodes. Settled area for a 180 km route unidirectional origin target ≈ 1.4 M nodes settled bidirectional origin target meeting ≈ 0.7 M nodes settled Area scales with the square of radius, so halving the radius quarters each disc — two of them still come to about half the original.

Implementation

NetworkX ships a correct implementation, and it should be the default:

# requires: networkx (pip install networkx)
import networkx as nx


def route(G: nx.DiGraph, source: int, target: int, weight: str = "travel_time_s"):
    """Shortest path with the built-in bidirectional search."""
    try:
        cost, path = nx.bidirectional_dijkstra(G, source, target, weight=weight)
    except nx.NetworkXNoPath:
        return None
    return {"cost": cost, "path": path}

Writing your own is only worth it when the expansion needs something the library does not offer — a turn-restricted transition check, say, or an early exit on a cost bound. The structure below shows the two parts that are easy to get wrong.

# requires: networkx, heapq (stdlib) (pip install networkx)
import heapq
import networkx as nx


def bidirectional(G: nx.DiGraph, s: int, t: int, weight: str = "travel_time_s"):
    """Bidirectional Dijkstra with the correct stopping condition."""
    if s == t:
        return 0.0, [s]
    R = G.reverse(copy=False)          # in-edges — required on a directed graph

    dist = [{s: 0.0}, {t: 0.0}]
    prev = [{s: None}, {t: None}]
    heaps = [[(0.0, s)], [(0.0, t)]]
    done = [set(), set()]
    best, meet = float("inf"), None
    side = 0

    while heaps[0] and heaps[1]:
        d, u = heapq.heappop(heaps[side])
        if u in done[side]:
            continue
        done[side].add(u)

        graph = G if side == 0 else R
        for v, data in graph[u].items():
            nd = d + data.get(weight, 1.0)
            if nd < dist[side].get(v, float("inf")):
                dist[side][v] = nd
                prev[side][v] = u
                heapq.heappush(heaps[side], (nd, v))
            # A node seen by both sides is a candidate meeting point
            if v in dist[1 - side]:
                total = nd + dist[1 - side][v]
                if total < best:
                    best, meet = total, v

        # Stop only when no cheaper meeting can still exist
        if heaps[0] and heaps[1] and heaps[0][0][0] + heaps[1][0][0] >= best:
            break
        side = 1 - side

    if meet is None:
        raise nx.NetworkXNoPath(f"no path {s} -> {t}")

    forward, node = [], meet
    while node is not None:
        forward.append(node)
        node = prev[0][node]
    backward, node = [], prev[1][meet]
    while node is not None:
        backward.append(node)
        node = prev[1][node]
    return best, list(reversed(forward)) + backward

Two lines carry the correctness. G.reverse(copy=False) gives a view over in-edges rather than a copy, and without it the backward search follows out-edges — which means it happily travels the wrong way along every one-way street and returns a path no vehicle can drive.

The stopping condition is the other. Comparing the sum of the two frontier radii against the best meeting found is what guarantees optimality; stopping at the first shared node does not, because a cheaper meeting may sit just beyond one frontier. The resulting error is typically small, which is precisely why it survives testing.

One practical detail is which side to expand next. The implementation above alternates strictly, which keeps the two frontiers balanced and gives the best worst-case behaviour. An alternative is to expand whichever side currently has the smaller frontier, which adapts to asymmetric graphs — a route from a dense city centre out to a rural depot has a much denser search space at one end than the other, and expanding the sparse side more often reaches the meeting point sooner. The gain is real but modest, and it comes with a subtlety: the stopping condition still has to compare both radii, so the bookkeeping does not simplify. Strict alternation is the right default and the adaptive variant is worth trying only when profiling shows one frontier consistently dwarfing the other.

Key parameters and tuning

Parameter Recommended value Notes
Implementation nx.bidirectional_dijkstra Correct and faster than a Python reimplementation
Reverse graph G.reverse(copy=False) A view, not a copy; copying doubles memory for nothing
Alternation strict, one pop per side Balanced frontiers give the best worst case
Stopping condition radii sum ≥ best meeting The first shared node is not sufficient
Route length threshold above ~20 km Below this the second frontier’s overhead dominates
Weight attribute explicit Defaulting to 1.0 silently returns a hop-count path
Use for isochrones never There is no target to search backward from

Integration points

Against A*. Where node coordinates exist and an admissible heuristic can be proven, A* is usually the better single-target choice, as covered in NetworkX Dijkstra vs A* for route calculation. Bidirectional search wins where the heuristic is unavailable or unprovable — contracted graphs, abstract networks, or time-dependent costs where the admissibility argument fails.

With turn restrictions. Combining bidirectional search with an edge-keyed frontier is possible but fiddly, because the backward search must apply restrictions in reverse. Where both are needed, it is usually simpler to keep a unidirectional edge-keyed search, per handling turn restrictions in routing graphs.

With graph backends. The saving is multiplicative with whatever the backend gives you. igraph’s C-core Dijkstra is already an order of magnitude faster than NetworkX, and bidirectional search on top of it compounds — see comparing Python graph libraries for OSM.

Where the second frontier starts paying Speedup relative to unidirectional Dijkstra is below one for routes under about five kilometres, crosses one near twenty, and plateaus around 1.9 times for routes beyond a hundred kilometres. Speedup against unidirectional Dijkstra, by route length 2.0× 1.0× 2 km 20 km 100 km 400 km break-even slower — second frontier overhead plateau near 1.9× The plateau is theoretical: two half-radius discs can never beat half the area, so a little under 2× is the ceiling for an unbounded search. Anything claiming much more than that is measuring a contracted graph or a heuristic, not bidirectional search alone. Search effort by method on one long route A unidirectional search settles 1.41 million nodes on a 180 kilometre route. Bidirectional halves that, an admissible A-star heuristic roughly thirds it, and a contracted hierarchy reduces it by a factor of thirty-five. Nodes settled on a 180 km route, by method unidirectional Dijkstra 1.41 M bidirectional Dijkstra 0.72 M A* with haversine 0.42 M contracted hierarchy 0.04 M Bidirectional search is the option available when no heuristic can be proven admissible and no contraction step is affordable. Where both are available, contraction wins decisively — but it costs hours of preprocessing and invalidates on every weight change.

Validation checklist

  • Costs match a unidirectional run. For a sample of pairs, the returned cost must equal nx.dijkstra_path_length exactly. A small positive difference means the stopping condition is premature.
  • One-way streets are respected. Route along a one-way street in the illegal direction and confirm no path is returned. A path here means the reverse search is following out-edges.
  • The spliced path is contiguous. Assert that every consecutive pair in the returned path is an edge in the graph. A gap means the meeting node was duplicated or dropped during reconstruction.
  • Short routes fall back. Confirm the code selects the unidirectional path below the length threshold, or accept the small loss knowingly.
  • The weight attribute is explicit. Assert that the attribute exists on every edge. A missing attribute defaults to unit weight and silently returns a hop-count path.