floyd_warshall

Floyd-Warshall 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	`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

Values

detect_negative_cycle

</>

pub fn detect_negative_cycle(
  distances: dict.Dict(#(Int, Int), e),
  nodes: List(Int),
  zero: e,
  compare: fn(e, e) -> order.Order,
) -> Bool

Detects if there’s a negative cycle by checking if any node has negative distance to itself

floyd_warshall

</>

pub fn floyd_warshall(
  in graph: model.Graph(n, e),
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> Result(dict.Dict(#(Int, Int), e), Nil)

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

Time Complexity: O(V³)

Returns an error if a negative cycle is detected.

floyd_warshall_float

</>

pub fn floyd_warshall_float(
  in graph: model.Graph(n, Float),
) -> Result(dict.Dict(#(Int, Int), Float), Nil)

Computes all-pairs shortest paths with float weights.

This is a convenience wrapper around floyd_warshall that uses:

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

Warning

Float arithmetic has precision limitations. Negative cycles might not be detected reliably due to floating-point errors.

floyd_warshall_int

</>

pub fn floyd_warshall_int(
  in graph: model.Graph(n, Int),
) -> Result(dict.Dict(#(Int, Int), Int), Nil)

Computes all-pairs shortest paths with integer weights.

This is a convenience wrapper around floyd_warshall that uses:

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

Example

let result = floyd_warshall.floyd_warshall_int(graph)
// => Ok(Dict([#(#(1, 2), 10), #(#(1, 3), 25), ...]))

When to Use

Use this for dense graphs where you need all-pairs distances with Int weights. For sparse graphs or single-source queries, prefer Dijkstra. Returns Error(Nil) if a negative cycle is detected.