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

[Floyd-Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)
for all-pairs shortest paths in weighted graphs.

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes
in a single execution. It uses dynamic programming to iteratively improve shortest
path estimates by considering each node as a potential intermediate vertex.

## Algorithm

| Algorithm | Function | Complexity | Best For |
|-----------|----------|------------|----------|
| [Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) | `floyd_warshall/4` | O(V³) | Dense graphs, all-pairs paths |

## Key Concepts

- **Dynamic Programming**: Builds solution from smaller subproblems
- **K-Intermediate Nodes**: After k iterations, paths use only nodes {1,...,k} as intermediates
- **Path Reconstruction**: Predecessor matrix allows full path recovery
- **Transitive Closure**: Can be adapted for reachability (boolean weights)

## The DP Recurrence

```
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
```

For each intermediate node k, check if going through k improves the path from i to j.

## Comparison with Running Dijkstra V Times

| Approach | Complexity | Best For |
|----------|------------|----------|
| Floyd-Warshall | O(V³) | Dense graphs (E ≈ V²) |
| V × Dijkstra | O(V(V+E) log V) | Sparse graphs |
| Johnson's | O(V² log V + VE) | Sparse graphs with negative weights |

**Rule of thumb**: Use Floyd-Warshall when E > V × log V (fairly dense)

## Negative Cycles

The algorithm can detect negative cycles: after completion, if any node has
dist[node][node] < 0, a negative cycle exists.

## Variants

- **Transitive Closure**: Use boolean OR instead of min-plus (Warshall's algorithm)
- **Successor Matrix**: Track next hop for path reconstruction

## Use Cases

- **All-pairs routing**: Precompute distances for fast lookup
- **Transitive closure**: Reachability queries in databases
- **Centrality metrics**: Closeness and betweenness calculations
- **Graph analysis**: Detecting negative cycles

## History

Published independently by Robert Floyd (1962), Stephen Warshall (1962),
and Bernard Roy (1959). Floyd's version included path reconstruction.

## References

- [Wikipedia: Floyd-Warshall Algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)
- [CP-Algorithms: Floyd-Warshall](https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html)

# `distance_matrix`

```elixir
@type distance_matrix() :: %{required({Yog.node_id(), Yog.node_id()}) =&gt; any()}
```

Distance matrix: map from `{from, to}` tuple to distance.

# `detect_negative_cycle?`

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

Detects whether the graph contains a negative cycle.

More efficient than running the full algorithm - returns early as soon as
a negative cycle is detected during the k iterations.

# `floyd_warshall`

```elixir
@spec floyd_warshall(Yog.graph(), any(), (any(), any() -&gt; any()), (any(), any() -&gt;
                                                               :lt | :eq | :gt)) ::
  {:ok, distance_matrix()} | {:error, :negative_cycle}
```

Computes shortest paths between all pairs of nodes using Floyd-Warshall.

**Time Complexity:** O(V³)

Returns `{:ok, distance_matrix}` on success, or `{:error, :negative_cycle}`
if a negative cycle is detected.

## Parameters

- `graph` - The graph to analyze
- `zero` - Identity element for addition
- `add` - Function to add two weights
- `compare` - Function to compare two weights

## Examples

    # Triangle graph with all-pairs distances
    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: 4)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 10)
    iex> compare = &Yog.Utils.compare/2
    iex> {:ok, distances} = Yog.Pathfinding.FloydWarshall.floyd_warshall(graph, 0, &(&1 + &2), compare)
    iex> # Shortest path from 1 to 3 should be 1->2->3 = 5, not direct 10
    ...> distances[{1, 3}]
    5

    # Negative cycle detection
    iex> bad_graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 1, with: -3)
    iex> compare = &Yog.Utils.compare/2
    iex> Yog.Pathfinding.FloydWarshall.floyd_warshall(bad_graph, 0, &(&1 + &2), compare)
    {:error, :negative_cycle}

---

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