Yog.FSharp
Getting Started Examples API Reference GitHub

FloydWarshall Module

Namespace: Yog.Pathfinding
Assembly: Yog.FSharp.dll

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

floydWarshall

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.

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.

Functions and values

Function or value Description

detectNegativeCycle zero compare distances nodes

Full Usage: detectNegativeCycle zero compare distances nodes

Parameters:
Returns: bool

true if a negative cycle is detected, false otherwise.

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

Parameters

  • zero: The zero/neutral element for the weight type
  • compare: Comparison function for weights
  • distances: Current distance map from Floyd-Warshall
  • nodes: List of node IDs to check

Algorithm

After Floyd-Warshall completes, if any node has dist[node][node] < 0, there's a negative cycle reachable from that node.

zero : 'e
compare : 'e -> 'e -> int
distances : Map<(NodeId * NodeId), 'e>
nodes : NodeId list
Returns: bool

true if a negative cycle is detected, false otherwise.

floydWarshall zero add compare graph

Full Usage: floydWarshall zero add compare graph

Parameters:
    zero : 'e
    add : 'e -> 'e -> 'e
    compare : 'e -> 'e -> int
    graph : Graph<'n, 'e>

Returns: Result<Map<(NodeId * NodeId), 'e>, unit>
  • Ok distances: Map from (source, target) pairs to shortest distance
  • Error (): If a negative cycle is detected

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

Type Parameters

  • 'e: The edge weight type (must support zero, addition, comparison)

Parameters

  • zero: The identity element for addition (e.g., 0, 0.0)
  • add: Addition function for combining path weights
  • compare: Comparison function returning int (< 0, 0, > 0)
  • graph: Input graph

Algorithm

Dynamic programming approach with relaxation:

1: 

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

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

// Compute all-pairs shortest paths
let result = floydWarshall 0 (+) compare graph

match result with
| Ok distances ->
    // Get distance from node 0 to node 3
    let d03 = distances |> Map.tryFind (0, 3)
| Error () ->
    printfn "Graph contains a negative cycle!"

Warning

Returns Error if the graph contains a negative cycle. In this case, shortest paths are undefined (they can be infinitely negative).

val min: e1: 'T -> e2: 'T -> 'T (requires comparison)
val compare: e1: 'T -> e2: 'T -> int (requires comparison)
union case Result.Ok: ResultValue: 'T -> Result<'T,'TError>
Multiple items
module Map from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> = interface IReadOnlyDictionary<'Key,'Value> interface IReadOnlyCollection<KeyValuePair<'Key,'Value>> interface IEnumerable interface IStructuralEquatable interface IComparable interface IEnumerable<KeyValuePair<'Key,'Value>> interface ICollection<KeyValuePair<'Key,'Value>> interface IDictionary<'Key,'Value> new: elements: ('Key * 'Value) seq -> Map<'Key,'Value> member Add: key: 'Key * value: 'Value -> Map<'Key,'Value> ...

--------------------
new: elements: ('Key * 'Value) seq -> Map<'Key,'Value>
val tryFind: key: 'Key -> table: Map<'Key,'T> -> 'T option (requires comparison)
union case Result.Error: ErrorValue: 'TError -> Result<'T,'TError>
val printfn: format: Printf.TextWriterFormat<'T> -> 'T

zero : 'e
add : 'e -> 'e -> 'e
compare : 'e -> 'e -> int
graph : Graph<'n, 'e>
Returns: Result<Map<(NodeId * NodeId), 'e>, unit>

  • Ok distances: Map from (source, target) pairs to shortest distance
  • Error (): If a negative cycle is detected

floydWarshallFloat graph

Full Usage: floydWarshallFloat graph

Parameters:
    graph : Graph<'n, float>

Returns: Result<Map<(NodeId * NodeId), float>, unit>
  • Ok distances: Map of shortest distances
  • Error (): If negative cycle detected

Computes all-pairs shortest paths with float weights.

Parameters

  • graph: Input graph with float edge weights

Note

Uses compare for float comparison. NaN values may cause unexpected behavior.

graph : Graph<'n, float>
Returns: Result<Map<(NodeId * NodeId), float>, unit>

  • Ok distances: Map of shortest distances
  • Error (): If negative cycle detected

floydWarshallInt graph

Full Usage: floydWarshallInt graph

Parameters:
Returns: Result<Map<(NodeId * NodeId), int>, unit>
  • Ok distances: Map of shortest distances
  • Error (): If negative cycle detected

Computes all-pairs shortest paths with integer weights.

Parameters

  • graph: Input graph with int edge weights

Example

1: 
2: 
3: 
4: 
5: 

let result = floydWarshallInt graph
// Access distance from 0 to 5
match result with
| Ok d -> d |> Map.tryFind (0, 5)
| Error () -> None
val result: Result<Map<(int * int),obj>,unit>
union case Result.Ok: ResultValue: 'T -> Result<'T,'TError>
val d: Map<(int * int),obj>
Multiple items
module Map from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> = interface IReadOnlyDictionary<'Key,'Value> interface IReadOnlyCollection<KeyValuePair<'Key,'Value>> interface IEnumerable interface IStructuralEquatable interface IComparable interface IEnumerable<KeyValuePair<'Key,'Value>> interface ICollection<KeyValuePair<'Key,'Value>> interface IDictionary<'Key,'Value> new: elements: ('Key * 'Value) seq -> Map<'Key,'Value> member Add: key: 'Key * value: 'Value -> Map<'Key,'Value> ...

--------------------
new: elements: ('Key * 'Value) seq -> Map<'Key,'Value>
val tryFind: key: 'Key -> table: Map<'Key,'T> -> 'T option (requires comparison)
union case Result.Error: ErrorValue: 'TError -> Result<'T,'TError>
union case Option.None: Option<'T>

graph : Graph<'n, int>
Returns: Result<Map<(NodeId * NodeId), int>, unit>

  • Ok distances: Map of shortest distances
  • Error (): If negative cycle detected