10.12 Accelerating Searches with Bidirectional Search

Many shortest-path algorithms begin at the source and gradually expand outward until the target is reached. This works well, but it often explores far more of the graph than necessary.

Consider finding a route between two cities on opposite sides of a large road network. A traditional search expands a growing region from the source. Much of that exploration occurs far from the destination.

An alternative strategy is surprisingly simple:

• Search forward from the source.
• Search backward from the destination.
• Stop when the two searches meet.

This technique is called bidirectional search.

When applicable, bidirectional search can reduce exploration dramatically and often provides one of the largest practical speedups available for shortest-path problems.

Problem

Given a source vertex and a target vertex in an unweighted graph, find the shortest path while minimizing the number of explored vertices.

Consider:

A - B - C - D - E - F - G

A traditional BFS starting at A explores:

A
A B
A B C
A B C D
A B C D E
A B C D E F
A B C D E F G

Most of the graph is visited.

A bidirectional search expands from both ends:

A -> B -> C -> D
G -> F -> E -> D

The searches meet near the middle.

Solution

Maintain two BFS frontiers:

• Forward search from the source
• Reverse search from the target

Terminate when a vertex is discovered by both searches.

package main

import "fmt"

func bidirectionalBFS(
	graph [][]int,
	source int,
	target int,
) int {

	if source == target {
		return 0
	}

	n := len(graph)

	distFromSource := make([]int, n)
	distFromTarget := make([]int, n)

	for i := 0; i < n; i++ {
		distFromSource[i] = -1
		distFromTarget[i] = -1
	}

	queueSource := []int{source}
	queueTarget := []int{target}

	distFromSource[source] = 0
	distFromTarget[target] = 0

	headSource := 0
	headTarget := 0

	for headSource < len(queueSource) &&
		headTarget < len(queueTarget) {

		if headSource < len(queueSource) {
			v := queueSource[headSource]
			headSource++

			for _, next := range graph[v] {
				if distFromSource[next] != -1 {
					continue
				}

				distFromSource[next] =
					distFromSource[v] + 1

				queueSource =
					append(queueSource, next)

				if distFromTarget[next] != -1 {
					return distFromSource[next] +
						distFromTarget[next]
				}
			}
		}

		if headTarget < len(queueTarget) {
			v := queueTarget[headTarget]
			headTarget++

			for _, next := range graph[v] {
				if distFromTarget[next] != -1 {
					continue
				}

				distFromTarget[next] =
					distFromTarget[v] + 1

				queueTarget =
					append(queueTarget, next)

				if distFromSource[next] != -1 {
					return distFromSource[next] +
						distFromTarget[next]
				}
			}
		}
	}

	return -1
}

func main() {
	graph := [][]int{
		{1},
		{0, 2},
		{1, 3},
		{2, 4},
		{3, 5},
		{4, 6},
		{5},
	}

	fmt.Println(
		bidirectionalBFS(graph, 0, 6),
	)
}

Output:

6

The shortest path contains six edges.

Why Bidirectional Search Works

Ordinary BFS explores vertices in increasing distance order.

Suppose the shortest path length is:

d

A standard search explores roughly all vertices within distance:

d

of the source.

Bidirectional search instead explores:

d / 2

from each side.

This may appear like a small change.

It is not.

Understanding the Branching Factor

Suppose each vertex has:

b

neighbors on average.

A traditional BFS explores approximately:

1 + b + b² + ... + bᵈ

vertices.

This grows approximately as:

bᵈ

A bidirectional search explores:

2 × (1 + b + b² + ... + b^(d/2))

which grows approximately as:

2b^(d/2)

The difference is enormous.

For example:

Branching Factor	Distance	BFS	Bidirectional
10	6	1,000,000	2,000
10	8	100,000,000	20,000
10	10	10,000,000,000	200,000

This exponential reduction explains the popularity of bidirectional search.

Visualizing the Search

Traditional BFS:

          S
       / /|\ \\n      / / | \ \\n     / /  |  \ \\n    ... expanding ...

The frontier grows outward continuously.

Bidirectional BFS:

S ---> ---> <--- <--- G

The searches meet near the center.

Only a fraction of the graph must be explored.

Detecting the Meeting Point

The algorithm maintains two distance arrays.

distFromSource[]
distFromTarget[]

Whenever a vertex becomes known to both searches:

if distFromTarget[next] != -1

or

if distFromSource[next] != -1

the shortest path has been discovered.

Its length is:

distance from source
+
distance from target

The meeting vertex acts as the connection point.

Path Reconstruction

Distances provide the path length.

To reconstruct the actual route, store predecessor arrays for both searches.

parentSource[]
parentTarget[]

When the searches meet:

source -> meeting vertex

is reconstructed using:

parentSource

and

meeting vertex -> target

is reconstructed using:

parentTarget

The two halves are concatenated.

This produces the complete shortest path.

Bidirectional Dijkstra

The same idea extends to weighted graphs.

Run:

• Dijkstra from the source
• Dijkstra from the target

Maintain two priority queues.

The searches stop when the best possible future path can no longer improve the current answer.

The implementation is significantly more complex than bidirectional BFS, but the underlying idea remains identical.

Large road-navigation systems frequently employ bidirectional variants.

Reverse Graphs

For directed graphs, the backward search cannot simply follow outgoing edges.

Instead, construct a reverse graph.

If:

A -> B

exists in the original graph, then:

B -> A

exists in the reverse graph.

The forward search uses the original graph.

The backward search uses the reversed graph.

This allows both searches to move toward each other correctly.

When Bidirectional Search Helps

The technique works best when:

• Source and target are known.
• The graph is large.
• The branching factor is significant.
• A single shortest path is needed.

Examples include:

• Navigation systems
• Social-network path finding
• State-space search
• Puzzle solving
• Route planning

The larger the graph, the greater the benefit.

When Bidirectional Search Does Not Help

If shortest paths to every vertex are required, bidirectional search is usually inappropriate.

For example:

Single-source shortest paths
All-pairs shortest paths
Reachability analysis

remain better suited to BFS, Dijkstra, Bellman-Ford, or Floyd-Warshall.

Bidirectional search is primarily a source-to-target optimization.

Discussion

The most important lesson is that shortest-path performance often depends more on search space reduction than on data-structure optimization.

Replacing a heap with a faster heap may improve performance by a constant factor.

Reducing the explored search space from:

bᵈ

to:

2b^(d/2)

changes the problem fundamentally.

This distinction appears repeatedly in algorithm design.

The largest gains often come from avoiding work rather than performing work more efficiently.

Complexity

Worst-case complexity remains similar to ordinary BFS.

Operation	Complexity
Forward BFS	O(V + E)
Reverse BFS	O(V + E)
Total worst case	O(V + E)
Memory usage	O(V)

The theoretical bound does not change.

The practical number of explored vertices often decreases dramatically.

Common Mistakes

Do not terminate as soon as the two frontiers touch. The meeting condition must preserve shortest-path correctness.

Do not use the original graph for the backward search in directed graphs.

Do not assume the first meeting vertex is necessarily the geometric midpoint of the path.

Do not forget that path reconstruction requires two predecessor trees.

Do not expect benefits when the graph diameter is very small.

Practical Applications

Bidirectional search appears in:

• GPS routing
• Road-navigation engines
• Airline route planning
• Social-network connection search
• Puzzle solvers
• State-space search systems
• Robotics
• Logistics optimization

Many large-scale routing systems combine bidirectional search with heuristic techniques such as A*.

Takeaway

Bidirectional search reduces shortest-path exploration by searching simultaneously from the source and the destination. Instead of exploring an entire search radius from one side, it explores roughly half the distance from each side and meets in the middle. The resulting reduction in explored vertices can be exponential in practice, making bidirectional search one of the most effective optimizations available for source-to-target shortest-path problems.