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

Bellman-Ford algorithm for single-source shortest paths with negative weight support.

Bellman-Ford can handle graphs with negative edge weights and detects negative
cycles. It's slower than Dijkstra but more versatile.

## Algorithm Characteristics

- **Time Complexity**: O(V × E)
- **Space Complexity**: O(V)
- **Requirements**: No negative cycles (detects them)
- **Optimality**: Optimal for graphs without negative cycles

## When to Use

- When edge weights may be negative
- When you need to detect negative cycles
- For all-pairs shortest paths (via V runs)
- When Dijkstra's non-negative weight requirement can't be met

## Negative Cycles

cost). Bellman-Ford detects this case.

## 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"]; C [label="C"]; D [label="D"];
  S -> A [label="4", color="#ff5555", penwidth=2.5];
  S -> B [label="3"];
  A -> B [label="-2", color="#ff5555", penwidth=2.5];
  A -> C [label="4"];
  B -> C [label="-3", color="#ff5555", penwidth=2.5];
  B -> D [label="1"];
  C -> D [label="2", color="#ff5555", penwidth=2.5];
}
</div>

    iex> alias Yog.Pathfinding.BellmanFord
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"S", "A", 4}, {"S", "B", 3}, {"A", "B", -2},
    ...>   {"A", "C", 4}, {"B", "C", -3}, {"B", "D", 1}, {"C", "D", 2}
    ...> ])
    iex> {:ok, path} = BellmanFord.bellman_ford(graph, "S", "D")
    iex> path.nodes
    ["S", "A", "B", "C", "D"]
    iex> path.weight
    1
    iex> # Detect unreachable goal
    iex> BellmanFord.bellman_ford(graph, "S", "NONEXISTENT")
    {:error, :no_path}

### Negative Cycles

<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  X [label="X"]; Y [label="Y"]; Z [label="Z"];
  X -> Y [label="1", color="#ff5555", penwidth=2.5];
  Y -> Z [label="1", color="#ff5555", penwidth=2.5];
  Z -> X [label="-3", color="#ff5555", penwidth=2.5];
}
</div>

    iex> cycle_graph = Yog.from_edges(:directed, [
    ...>   {"X", "Y", 1}, {"Y", "Z", 1}, {"Z", "X", -3}
    ...> ])
    iex> BellmanFord.bellman_ford(cycle_graph, "X", "Z")
    {:error, :negative_cycle}

# `implicit_result`

```elixir
@type implicit_result(weight) ::
  {:ok, weight} | {:error, :negative_cycle} | {:error, :no_goal}
```

Result type for implicit Bellman-Ford queries

# `result`

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

Result type for Bellman-Ford shortest path queries

# `bellman_ford`

```elixir
@spec bellman_ford(keyword()) :: result()
```

Find shortest path using Bellman-Ford with keyword options.

## Options

  * `:in` - The graph to search
  * `:from` - Starting node
  * `:to` - Target node
  * `:zero` - Identity value for the weight type
  * `:add` - Function to add two weights
  * `:compare` - Function to compare weights (`:lt`, `:eq`, `:gt`)

## Examples

    Pathfinding.BellmanFord.bellman_ford(
      in: graph,
      from: :a,
      to: :c,
      zero: 0,
      add: &(&1 + &2),
      compare: &Yog.Utils.compare/2
    )

# `bellman_ford`

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

Find the shortest path between two nodes using Bellman-Ford.

## Parameters

  * `graph` - The graph to search
  * `from` - Starting node
  * `to` - Target node
  * `zero` - Identity value for the weight type
  * `add` - Function to add two weights
  * `compare` - Function to compare weights (`:lt`, `:eq`, `:gt`)

## Returns

  * `{:ok, path}` - A `Path` struct containing the nodes and weight
  * `{:error, :negative_cycle}` - A negative cycle was detected
  * `{:error, :no_path}` - No path exists between the nodes

## Examples

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(:a, nil)
    ...> |> Yog.add_node(:b, nil)
    ...> |> Yog.add_node(:c, nil)
    ...> |> Yog.add_edge_ensure(:a, :b, 4)
    ...> |> Yog.add_edge_ensure(:b, :c, -3)
    iex> compare = &Yog.Utils.compare/2
    iex> {:ok, path} = BellmanFord.bellman_ford(graph, :a, :c, 0, &(&1 + &2), compare)
    iex> path.nodes
    [:a, :b, :c]
    iex> path.weight
    1

    iex> # Graph with negative cycle
    iex> bad_graph = Yog.directed()
    ...> |> Yog.add_node(:a, nil)
    ...> |> Yog.add_node(:b, nil)
    ...> |> Yog.add_edge_ensure(:a, :b, 1)
    ...> |> Yog.add_edge_ensure(:b, :a, -3)
    iex> compare = &Yog.Utils.compare/2
    iex> BellmanFord.bellman_ford(bad_graph, :a, :b, 0, &(&1 + &2), compare)
    {:error, :negative_cycle}

# `has_negative_cycle?`

```elixir
@spec has_negative_cycle?(
  Yog.graph(),
  Yog.node_id(),
  any(),
  (any(), any() -&gt; any()),
  (any(), any() -&gt;
     :lt | :eq | :gt)
) ::
  boolean()
```

Checks if the graph contains a negative cycle reachable from the source.

# `implicit_bellman_ford`

```elixir
@spec implicit_bellman_ford(keyword()) :: implicit_result(any())
```

Implicit Bellman-Ford using keyword options.

## Options

  * `:from` - Starting state
  * `:successors_with_cost` - Function returning neighbors with costs
  * `:is_goal` - Function to check if a state is the goal
  * `:zero` - Identity value for the weight type
  * `:add` - Function to add two weights
  * `:compare` - Function to compare weights
  * `:max_iterations` - Maximum iterations before giving up (default: 1000)

## Examples

    Pathfinding.implicit_bellman_ford(
      from: 1,
      successors_with_cost: fn n -> [{n+1, -1}] end,
      is_goal: fn n -> n == 10 end,
      zero: 0,
      add: &(&1 + &2),
      compare: &Yog.Utils.compare/2
    )

# `implicit_bellman_ford`

```elixir
@spec implicit_bellman_ford(
  state,
  (state -&gt; [{state, cost}]),
  (state -&gt; boolean()),
  cost,
  (cost, cost -&gt; cost),
  (cost, cost -&gt; :lt | :eq | :gt),
  non_neg_integer()
) :: implicit_result(cost)
when state: var, cost: var
```

Run Bellman-Ford on an implicit (generated) graph.

Similar to implicit Dijkstra, but supports negative edge weights and can
detect negative cycles.

## Parameters

  * `from` - Starting state
  * `successors` - Function `state -> [{neighbor, cost}]`
  * `is_goal` - Function `state -> boolean` to check if goal reached
  * `zero` - Identity value for the weight type
  * `add` - Function to add two weights
  * `compare` - Function to compare weights

## Returns

  * `{:ok, cost}` - Minimum cost to reach goal
  * `{:error, :negative_cycle}` - A negative cycle was found
  * `{:error, :no_goal}` - Goal is unreachable

## Examples

    # Search with negative weights
    iex> successors = fn
    ...>   1 -> [{2, -1}]
    ...>   2 -> [{3, -2}]
    ...>   3 -> [{4, -3}]
    ...>   4 -> []
    ...> end
    iex> {:ok, cost} = BellmanFord.implicit_bellman_ford(
    ...>   1, successors, fn x -> x == 4 end,
    ...>   0, &(&1 + &2), &Yog.Utils.compare/2
    ...> )
    iex> cost
    -6

# `implicit_bellman_ford_by`

```elixir
@spec implicit_bellman_ford_by(keyword()) :: implicit_result(any())
```

Implicit Bellman-Ford with key function using keyword options.

## Options

  * `:from` - Starting state
  * `:successors_with_cost` - Function returning neighbors with costs
  * `:visited_by` - Function to extract a key for visited tracking
  * `:is_goal` - Function to check if a state is the goal
  * `:zero` - Identity value for the weight type
  * `:add` - Function to add two weights
  * `:compare` - Function to compare weights

# `implicit_bellman_ford_by`

```elixir
@spec implicit_bellman_ford_by(
  state,
  (state -&gt; [{state, cost}]),
  (state -&gt; term()),
  (state -&gt; boolean()),
  cost,
  (cost, cost -&gt; cost),
  (cost, cost -&gt; :lt | :eq | :gt),
  non_neg_integer()
) :: implicit_result(cost)
when state: var, cost: var
```

Implicit Bellman-Ford with a key function for visited state tracking.

Similar to `implicit_bellman_ford/7`, but uses a key function for visited tracking.

## Parameters

  * `from` - Starting state
  * `successors` - Function `state -> [{neighbor, cost}]`
  * `key_fn` - Function `state -> key` for visited tracking
  * `is_goal` - Function `state -> boolean` to check if goal reached
  * `zero` - Identity value for the weight type
  * `add` - Function to add two weights
  * `compare` - Function to compare weights
  * `max_iterations` - Maximum iterations before giving up (default: 1000)

# `reconstruct_path`

```elixir
@spec reconstruct_path(
  %{required(Yog.node_id()) =&gt; Yog.node_id()},
  Yog.node_id(),
  Yog.node_id(),
  any()
) ::
  Yog.Pathfinding.Path.t()
```

Reconstructs a path from the predecessor map returned by Bellman-Ford.

# `relaxation_passes`

```elixir
@spec relaxation_passes(
  Yog.graph(),
  Yog.node_id(),
  any(),
  (any(), any() -&gt; any()),
  (any(), any() -&gt;
     :lt | :eq | :gt)
) ::
  %{required(Yog.node_id()) =&gt; any()}
```

Computes relaxation passes for all-pairs shortest paths.

Returns a map of all node distances after V-1 relaxation passes.

---

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