# `Yog.Pathfinding.Bidirectional`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/pathfinding/bidirectional.ex#L1)

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

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.

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 (up to 500x faster for long paths)

## Requirements

- Target node must be known in advance (unlike Dijkstra, which can route many at once).
- Designed for point-to-point queries.

## Examples

<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  S [label="S"]; A [label="A"]; B [label="B"];
  M [label="M", color="#6366f1", penwidth=2];
  C [label="C"]; D [label="D"]; T [label="T"];
  S -> A [label="2", color="#6366f1", penwidth=2.5];
  A -> M [label="2", color="#6366f1", penwidth=2.5];
  S -> B [label="5"];
  B -> M [label="1"];
  M -> C [label="2", color="#6366f1", penwidth=2.5];
  C -> T [label="2", color="#6366f1", penwidth=2.5];
  M -> D [label="5"];
  D -> T [label="1"];
}
</div>

    iex> alias Yog.Pathfinding.Bidirectional
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"S", "A", 2}, {"A", "M", 2}, {"S", "B", 5}, {"B", "M", 1},
    ...>   {"M", "C", 2}, {"C", "T", 2}, {"M", "D", 5}, {"D", "T", 1}
    ...> ])
    iex> {:ok, path} = Bidirectional.shortest_path(graph, "S", "T")
    iex> path.nodes
    ["S", "A", "M", "C", "T"]
    iex> path.weight
    8

# `path_result`

```elixir
@type path_result() :: {:ok, Yog.Pathfinding.Path.t()} | :error
```

Result type for shortest path queries

# `shortest_path`

```elixir
@spec shortest_path(keyword()) :: path_result()
```

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

## Options

  * `:in` - The graph
  * `:from` - The starting node ID
  * `:to` - The target node ID
  * `:zero` - The identity element for weights (e.g. `0`)
  * `:add` - Weight addition function (e.g. `fn a, b -> a + b end`)
  * `:compare` - Comparison function (e.g. `&Yog.Utils.compare/2`)

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 10)
    iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path(
    ...>   in: graph, from: 1, to: 3,
    ...>   zero: 0, add: &+/2, compare: &Yog.Utils.compare/2
    ...> )
    iex> path.nodes
    [1, 2, 3]
    iex> path.weight
    15

# `shortest_path`

```elixir
@spec shortest_path(
  Yog.t(),
  Yog.node_id(),
  Yog.node_id(),
  weight,
  (weight, weight -&gt; weight),
  (weight, weight -&gt;
     :lt
     | :eq
     | :gt)
) ::
  path_result() | :error
when weight: var
```

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

## Parameters

  * `graph` - The graph to search
  * `from` - The starting node ID
  * `to` - The target node ID
  * `zero` - The identity element for weights (e.g. `0`)
  * `add` - Weight addition function (e.g. `fn a, b -> a + b end`)
  * `compare` - Comparison function returning `:lt`, `:eq`, or `:gt`

## Returns

  * `{:ok, path}` - A `Path` struct containing the nodes and total weight
  * `:error` - No path exists between the nodes

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 10)
    iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path(graph, 1, 3, 0, &+/2, &Yog.Utils.compare/2)
    iex> path.nodes
    [1, 2, 3]
    iex> path.weight
    15

# `shortest_path_unweighted`

```elixir
@spec shortest_path_unweighted(keyword()) :: path_result()
```

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.

## Options

  * `:in` - The graph
  * `:from` - The starting node ID
  * `:to` - The target node ID

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path_unweighted(in: graph, from: 1, to: 3)
    iex> path.nodes
    [1, 2, 3]
    iex> path.weight
    2
    iex> Yog.Pathfinding.Bidirectional.shortest_path_unweighted(in: graph, from: 1, to: 99)
    :error

# `shortest_path_unweighted`

```elixir
@spec shortest_path_unweighted(Yog.t(), Yog.node_id(), Yog.node_id()) ::
  path_result() | :error
```

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

## Parameters

  * `graph` - The graph to search
  * `from` - The starting node ID
  * `to` - The target node ID

## Returns

  * `{:ok, path}` - A `Path` struct containing the nodes and edge count
  * `:error` - No path exists between the nodes

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path_unweighted(graph, 1, 3)
    iex> path.nodes
    [1, 2, 3]
    iex> path.weight
    2
    iex> Yog.Pathfinding.Bidirectional.shortest_path_unweighted(graph, 1, 99)
    :error

---

*Consult [api-reference.md](api-reference.md) for complete listing*