bidirectional

Bidirectional search algorithms that meet in the middle for dramatic speedup.

These algorithms start two simultaneous searches - one from the source and one from the target - that meet in the middle. This can dramatically reduce the search space compared to single-direction search.

Performance Benefits

For a graph with branching factor b and depth d:

Standard BFS: O(b^d) nodes explored
Bidirectional BFS: O(2 × b^(d/2)) nodes explored

Example with b=10, d=6:

Standard: 10^6 = 1,000,000 nodes
Bidirectional: 2 × 10^3 = 2,000 nodes (500× faster!)

Algorithms

Algorithm	Function	Complexity	Best For
Bidirectional BFS	`shortest_path_unweighted/3`	O(b^(d/2))	Unweighted graphs
Bidirectional Dijkstra	`shortest_path/6`	O(b^(d/2) log b)	Weighted graphs

Requirements

Graph must be connected (otherwise no path exists)
For directed graphs: needs efficient reverse edge lookup (yog’s in_edges structure is perfect!)
Target node must be known in advance

Termination

The tricky part of bidirectional search is knowing when to stop:

BFS: Can stop as soon as frontiers touch
Dijkstra: Must continue until minimum distances from both sides exceed best path found

References

Values

shortest_path

</>

pub fn shortest_path(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> option.Option(path.Path(e))

Finds the shortest path in a weighted graph using bidirectional Dijkstra.

This is trickier than bidirectional BFS because we can’t stop as soon as the frontiers meet - we must continue until we can prove optimality.

Time Complexity: O((V + E) log V / 2) - approximately 2x faster than standard Dijkstra

Parameters

zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two weights
compare: Function to compare two weights

Example

bidirectional.shortest_path(
  in: graph,
  from: 1,
  to: 100,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare
)
// => Some(Path([1, 5, 20, 100], 42))

shortest_path_float

</>

pub fn shortest_path_float(
  in graph: model.Graph(n, Float),
  from start: Int,
  to goal: Int,
) -> option.Option(path.Path(Float))

Finds the shortest path using bidirectional Dijkstra with float weights.

Convenience wrapper that uses:

0.0 as the zero element
float.add for addition
float.compare for comparison

shortest_path_int

</>

pub fn shortest_path_int(
  in graph: model.Graph(n, Int),
  from start: Int,
  to goal: Int,
) -> option.Option(path.Path(Int))

Finds the shortest path using bidirectional Dijkstra with integer weights.

Convenience wrapper that uses:

0 as the zero element
int.add for addition
int.compare for comparison

shortest_path_unweighted

</>

pub fn shortest_path_unweighted(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
) -> option.Option(path.Path(Int))

Finds the shortest path in an unweighted graph using bidirectional BFS.

This runs BFS from both source and target simultaneously, stopping when the frontiers meet. Much faster than single-direction BFS for long paths.

Time Complexity: O(b^(d/2)) where b is branching factor and d is depth

Example

bidirectional.shortest_path_unweighted(
  in: graph,
  from: 1,
  to: 100
)
// => Some(Path([1, 5, 20, 100], 3))