yog - v3.1.0

yog/pathfinding/floyd_warshall

Floyd-Warshall algorithm for all-pairs shortest paths.

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.

✨ Search Document