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

Dijkstra's algorithm for single-source shortest paths.

Dijkstra's algorithm finds the shortest path from a source node to all other
reachable nodes in a graph with non-negative edge weights.

## Implementation Notes

This module uses a hybrid implementation:
- `shortest_path/6`, `implicit_dijkstra/6`, and `implicit_dijkstra_by/7`
  delegate to `AStar` with a zero heuristic (`fn _, _ -> 0 end` or `fn _ -> 0 end`),
  since Dijkstra's algorithm is mathematically equivalent to A* with zero heuristic.
- `single_source_distances/5` uses a native implementation since it computes
  distances to ALL nodes (A* requires a goal).

## Algorithm Characteristics

- **Time Complexity**: O((V + E) log V) with a binary heap
- **Space Complexity**: O(V)
- **Requirements**: Non-negative edge weights
- **Optimality**: Guaranteed optimal for graphs with non-negative weights

## When to Use

- When all edge weights are non-negative
- For single-source shortest path problems
- When you need paths to all nodes from a source
- As a baseline comparison for other algorithms

## Examples

<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  A [label="A"]; B [label="B"]; C [label="C"];
  D [label="D"]; E [label="E"]; F [label="F"];
  A -> B [label="4"];
  A -> C [label="2", color="#ff5555", penwidth=2.5];
  B -> D [label="5", color="#ff5555", penwidth=2.5];
  C -> B [label="1", color="#ff5555", penwidth=2.5];
  C -> D [label="8"];
  C -> E [label="10"];
  D -> E [label="2", color="#ff5555", penwidth=2.5];
  D -> F [label="6"];
  E -> F [label="2", color="#ff5555", penwidth=2.5];
}
</div>

    iex> alias Yog.Pathfinding.Dijkstra
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"A", "B", 4}, {"A", "C", 2}, {"B", "D", 5},
    ...>   {"C", "B", 1}, {"C", "D", 8}, {"C", "E", 10},
    ...>   {"D", "E", 2}, {"D", "F", 6}, {"E", "F", 2}
    ...> ])
    iex> compare = &Yog.Utils.compare/2
    iex> {:ok, path} = Dijkstra.shortest_path(graph, "A", "F", 0, &(&1 + &2), compare)
    iex> path.nodes
    ["A", "C", "B", "D", "E", "F"]
    iex> path.weight
    12
    iex> Dijkstra.single_source_distances(graph, "A", 0, &(&1 + &2), compare)
    %{"A" => 0, "C" => 2, "B" => 3, "D" => 8, "E" => 10, "F" => 12}

# `path_result`

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

Result type for shortest path queries

# `implicit_dijkstra`

```elixir
@spec implicit_dijkstra(keyword()) :: {:ok, any()} | :error
```

Implicit Dijkstra 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

## Examples

    Pathfinding.implicit_dijkstra(
      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_dijkstra`

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

Run Dijkstra on an implicit (generated) graph.

Instead of storing all edges explicitly, provide a successor function that
generates neighbors on demand. This is useful for:
- Infinite or very large graphs
- Grid-based pathfinding with dynamic obstacles
- Game state spaces

This function delegates to `Yog.Pathfinding.AStar.implicit_a_star/7` with
a zero heuristic (`fn _ -> 0 end`).

## 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 (default: 0)
  * `add` - Function to add two weights (default: `&Kernel.+/2`)
  * `compare` - Function to compare weights (default: `&Yog.Utils.compare/2`)

## Returns

  * `{:ok, cost}` - Minimum cost to reach goal
  * `:error` - Goal is unreachable

## Examples

    # Search on a linear chain: 1->2->3->4 with costs 1,2,3
    iex> successors = fn
    ...>   1 -> [{2, 1}]
    ...>   2 -> [{3, 2}]
    ...>   3 -> [{4, 3}]
    ...>   4 -> []
    ...> end
    iex> compare = &Yog.Utils.compare/2
    iex> {:ok, cost} = Dijkstra.implicit_dijkstra(
    ...>   1, successors, fn x -> x == 4 end,
    ...>   0, &(&1 + &2), compare
    ...> )
    iex> cost
    6

# `implicit_dijkstra_by`

```elixir
@spec implicit_dijkstra_by(keyword()) :: {:ok, any()} | :error
```

Implicit Dijkstra 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_dijkstra_by`

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

Implicit Dijkstra with a key function for visited state tracking.

Similar to `implicit_dijkstra/6`, but uses a key function to determine
when states should be considered "visited". This allows:
- Efficient pruning of equivalent states
- Custom equivalence relations beyond simple equality

This function delegates to `Yog.Pathfinding.AStar.implicit_a_star_by/8` with
a zero heuristic (`fn _ -> 0 end`).

## 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 (default: 0)
  * `add` - Function to add two weights (default: `&Kernel.+/2`)
  * `compare` - Function to compare weights (default: `&Yog.Utils.compare/2`)

## Examples

    iex> successors = fn
    ...>   {pos, _dir} when pos < 3 -> [{{pos + 1, :fwd}, 1}]
    ...>   _ -> []
    ...> end
    iex> key_fn = fn {pos, _dir} -> pos end
    iex> goal_fn = fn {pos, _dir} -> pos == 3 end
    iex> compare = &Yog.Utils.compare/2
    iex> {:ok, cost} = Dijkstra.implicit_dijkstra_by(
    ...>   {0, :start}, successors, key_fn,
    ...>   goal_fn, 0, &(&1 + &2), compare
    ...> )
    iex> cost
    3

# `shortest_path`

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

Find shortest path using 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.shortest_path(
      in: graph,
      from: :a,
      to: :c,
      zero: 0,
      add: &(&1 + &2),
      compare: &Yog.Utils.compare/2
    )

# `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()
when weight: var
```

Find the shortest path between two nodes using Dijkstra's algorithm.

This function delegates to `Yog.Pathfinding.AStar.a_star/7` with a zero
heuristic (`fn _, _ -> 0 end`), since Dijkstra's algorithm is mathematically
equivalent to A* with zero heuristic.

## Parameters

  * `graph` - The graph to search
  * `from` - Starting node
  * `to` - Target node
  * `zero` - Identity value for the weight type (default: 0)
  * `add` - Function to add two weights (default: `&Kernel.+/2`)
  * `compare` - Function to compare weights (default: `&Yog.Utils.compare/2`)

## Returns

  * `{:ok, path}` - A `Path` struct containing the nodes and total weight
  * `:error` - 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, 1)
    iex> compare = &Yog.Utils.compare/2
    iex> {:ok, path} = Dijkstra.shortest_path(graph, :a, :c, 0, &(&1 + &2), compare)
    iex> path.nodes
    [:a, :b, :c]
    iex> path.weight
    5
    iex> path.algorithm
    :dijkstra

# `single_source_distances`

```elixir
@spec single_source_distances(keyword()) :: %{required(Yog.node_id()) =&gt; any()}
```

Single-source distances using keyword options.

## Options

  * `:in` - The graph to search
  * `:from` - Source node
  * `:zero` - Identity value for the weight type
  * `:add` - Function to add two weights
  * `:compare` - Function to compare weights

## Examples

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

# `single_source_distances`

```elixir
@spec single_source_distances(
  Yog.t(),
  Yog.node_id(),
  weight,
  (weight, weight -&gt; weight),
  (weight, weight -&gt;
     :lt
     | :eq
     | :gt)
) ::
  %{required(Yog.node_id()) =&gt; weight}
when weight: var
```

Calculate single-source shortest distances to all reachable nodes.

Returns a map of node IDs to their shortest distance from the source.

This function uses a native implementation (not delegated to A*) because
A* requires a goal node, but this function computes distances to ALL nodes.

## Parameters

  * `graph` - The graph to search
  * `from` - Source node
  * `zero` - Identity value for the weight type (default: 0)
  * `add` - Function to add two weights (default: `&Kernel.+/2`)
  * `compare` - Function to compare weights (default: `&Yog.Utils.compare/2`)

## 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(:a, :c, 2)
    ...> |> Yog.add_edge_ensure(:b, :c, 1)
    iex> compare = &Yog.Utils.compare/2
    iex> Dijkstra.single_source_distances(graph, :a, 0, &(&1 + &2), compare)
    %{a: 0, b: 4, c: 2}

# `widest_path`

```elixir
@spec widest_path(Yog.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, Yog.Pathfinding.Path.t()} | :error
```

Find the widest path (maximum capacity path) between two nodes.

The widest path maximizes the minimum edge weight along the path (the bottleneck).
This is useful for network bandwidth routing, finding reliable paths, and
max-min fair allocation problems.

This is a simple modification of Dijkstra's algorithm:
- Initialize source capacity to `:infinity` (no bottleneck yet)
- Use `min/2` to combine capacities (bottleneck is the minimum edge)
- Use `>=` comparison to prioritize higher capacities (maximize)

## Parameters

  * `graph` - The graph to search
  * `from` - Starting node
  * `to` - Target node

## Returns

  * `{:ok, path}` - A `Path` struct containing the nodes and bottleneck capacity
  * `:error` - 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_node(:d, nil)
    ...> |> Yog.add_edge_ensure(:a, :b, 100)
    ...> |> Yog.add_edge_ensure(:a, :c, 50)
    ...> |> Yog.add_edge_ensure(:b, :d, 80)
    ...> |> Yog.add_edge_ensure(:c, :d, 200)
    iex> {:ok, path} = Dijkstra.widest_path(graph, :a, :d)
    iex> path.nodes
    [:a, :b, :d]
    iex> path.weight
    80
    iex> path.algorithm
    :widest_path

## Algorithm

Standard Dijkstra minimizes: `dist[v] = min(dist[u] + weight(u,v))`
Widest Path maximizes: `cap[v] = max(cap[v], min(cap[u], weight(u,v)))`

The path's "width" is the minimum edge weight along it. We want to
maximize this minimum (the bottleneck capacity).

## See Also

- `shortest_path/6` - Standard Dijkstra for shortest paths
- Wikipedia: https://en.wikipedia.org/wiki/Widest_path_problem

---

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