Is the meeting point always the geometric midpoint?

No. Search structure and expansion policy determine where the connection is found.

Can it handle weighted edges?

Yes, through an appropriate weighted algorithm; an unweighted routine minimizes edge count instead.

Is it useful when the goal is unknown?

The classic approach needs a defined backward starting set, which may be difficult or impractical for such tasks.

AI Glossary / Graphs and symbolic AI / Intermediate

Bidirectional search

Definition

Bidirectional search looks for a connection by searching forwards from a starting state and backwards from a goal. It maintains information from both directions and combines the partial paths when they connect, using an algorithm-specific stopping rule.

What it means

A conventional search starts at one end and discovers everything needed to reach the other. Bidirectional search asks whether two shallower explorations can find the same connection with less work.

The idea is especially attractive when the start and goal are clearly specified and predecessor states can be generated efficiently. In a directed graph, a backward step follows an incoming edge to a possible predecessor. It does not assume that a traveler or process can physically perform the original action in reverse.

Meeting is also a logical event rather than a requirement that two computations run on separate processors. One program can alternate between the two frontiers. The meeting point need not lie exactly halfway along the final path, and the two sides need not expand equal numbers of states.

The strategy includes unweighted shortest-path methods and cost-aware variants such as bidirectional Dijkstra. Their guarantees depend on the chosen algorithm, not merely on the presence of two searches.

How it works

Store a frontier and reached-state records for each direction. Forward records describe how a state was reached from the start. Backward records describe how it can lead towards the goal. Expanding a frontier generates appropriate successors or predecessors and checks for connections with the other side.

For an unweighted graph, a correctly organized bidirectional breadth-first search can return a path with the fewest edges. Preserving breadth levels and using a valid meeting rule matters; two arbitrary depth-first searches do not inherit that shortest-path guarantee.

For weighted graphs, maintain path costs and a best complete candidate. A suitable stopping condition must establish that unexplored combinations cannot improve that candidate. Simply returning the first contact can produce a more expensive route.

After a justified connection is found, reconstruct the start-to-meeting segment and the meeting-to-goal segment, keeping edge orientation correct.

Reverse generation can be difficult in planning problems. A goal may describe many states, or an action may have numerous possible predecessors. In such cases the backward side can erase the hoped-for savings.

Three practical examples

A navigation tool searches an unweighted connection map from both a departure point and a destination to minimize the number of links traversed.
A puzzle solver searches legal moves forwards and legal predecessor configurations backwards when the goal arrangement is fixed.
A graph-analysis service uses a weighted bidirectional shortest-path implementation to compare routes under nonnegative edge costs.

Think of it this way

Think of tracing a family connection using records from both named people. Each side builds a chain until the records connect, after which the chains can be joined.

The analogy does not imply that the first shared surname proves a relationship. Search states must match under a precise identity rule, just as a valid record connection needs more than a similar label. Nor does the analogy supply a shortest-path stopping proof.

Worked example

Joining two directed path fragments

Consider directed edges S→A, A→B, B→C and C→T, each with cost 1. Also include dead-end edge S→X. The desired route runs from S to T.

The forward search starts with S and discovers A and X. The backward search starts with T and discovers C because C has an edge into T. Expanding A discovers B; expanding C backwards also discovers B because B→C is an original edge.

The connection at B joins S→A→B to B→C→T. The complete path has four edges and total cost 4. Backward discovery of C from T does not assert that T→C exists.

For scale intuition, suppose an idealized tree-like search has branching factor 10 and solution depth 6. One full depth-6 expansion contains 1 + 10 + 100 + 1,000 + 10,000 + 100,000 + 1,000,000 = 1,111,111 nodes. Two depth-3 expansions contain 2 × 1,111 = 2,222 nodes before accounting for overlap. This is an illustrative growth comparison, not a runtime forecast for graphs with cycles or uneven branching.

Illustrative case study

Fictional case: Maple Paths adds reverse traversal to a dependency explorer. Its first prototype uses outgoing edges from both endpoints, which works on symmetric examples but fails on one-way dependencies.

The team changes the goal-side traversal to predecessor relationships and tests reconstructed paths against the original edge direction. It also keeps the unweighted hop-count service separate from a service that considers processing costs.

The lesson is that two-frontier architecture is only part of correctness. Direction, objective and termination must all match the question the user asked.

Common misconceptions and mistakes

Bidirectional means two processors are required. The searches can be interleaved in one process.
Backward search requires physically reversible actions. It requires a way to generate valid predecessors.
Any first meeting is a cheapest solution. Weighted and other variants need justified stopping rules.
Both sides must do equal work. Expansion policies can choose a more promising or smaller frontier.
The method always halves runtime. Benefits depend on graph shape, reverse-generation cost and implementation.

Business use

Bidirectional search can improve point-to-point services when target states are explicit and reverse links are available. Its suitability is less obvious for requests such as finding any acceptable plan among many vaguely specified goals.

Evaluate returned path validity and objective value before comparing speed. Include disconnected cases, one-way edges, highly asymmetric branching and repeated states. Record the memory used by both reached-state collections. For changing networks, use a consistent graph snapshot or a defined update policy so the two halves do not describe incompatible versions.

Check your understanding

A backward search from T discovers C through original edge C→T. Does that make T→C a valid forward step?

Answer: No. Reverse traversal is a computational way to find predecessors; reconstructed forward paths must respect the original edge directions.

Related terms

Breadth First Search
Shortest Paths
Dijkstra's algorithm
Directed graph
shortest path
predecessor
search frontier
path reconstruction
goal state

Learn next

Draw a directed graph with one short route, one long route and a dead end. Trace both reached sets and reconstruct their connection. Then assign unequal costs and explain why the fewest-edge route may no longer be the cheapest.

Directed graph

Sources

AIMA glossary, bidirectional search: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

NetworkX unweighted routine: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.unweighted.bidirectional_shortest_path.html

NetworkX weighted variant and restrictions: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bidirectional_dijkstra.html

Path and tree-size calculations are original illustrations.

Previous: Bidirectional language model Next: Bidirectional similarity