800 Fundamental

800-floyd-warshall — Floyd-Warshall Algorithm

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "800-floyd-warshall — Floyd-Warshall Algorithm" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Floyd-Warshall (1962) computes shortest paths between ALL pairs of vertices in a weighted graph in O(V³) time. Key difference from OCaml: 1. **All

Tutorial

The Problem

Floyd-Warshall (1962) computes shortest paths between ALL pairs of vertices in a weighted graph in O(V³) time. Unlike Dijkstra (single source) or Bellman-Ford (single source with negative weights), Floyd-Warshall solves the all-pairs problem directly. It is used in network distance matrices, routing table computation, social graph analysis (degree of separation), and computing transitive closures.

🎯 Learning Outcomes

• Initialize the distance matrix from edges and set dist[i][i] = 0

• Apply the DP recurrence: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

• Understand why the order of loops (k outer, then i, j) is correct

• Detect negative cycles via dist[i][i] < 0 after the algorithm

• Use Floyd-Warshall as a transitive closure algorithm (boolean variant)

Code Example

#![allow(clippy::all)]
//! # Floyd-Warshall Algorithm

pub fn floyd_warshall(n: usize, edges: &[(usize, usize, i32)]) -> Vec<Vec<i32>> {
    let mut dist = vec![vec![i32::MAX / 2; n]; n];
    for i in 0..n {
        dist[i][i] = 0;
    }
    for &(u, v, w) in edges {
        dist[u][v] = w;
    }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    dist
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_floyd() {
        let edges = [(0, 1, 3), (0, 2, 8), (1, 2, 2), (2, 0, 5)];
        let dist = floyd_warshall(3, &edges);
        assert_eq!(dist[0][2], 5);
    }
}

(* Floyd-Warshall — all-pairs shortest paths O(V³) *)
let infinity = max_int / 2

let floyd_warshall n edges =
  let dist = Array.init n (fun i -> Array.init n (fun j ->
    if i = j then 0 else infinity
  )) in
  let next = Array.init n (fun _ -> Array.make n (-1)) in
  List.iter (fun (u, v, w) ->
    if w < dist.(u).(v) then begin
      dist.(u).(v) <- w;
      next.(u).(v) <- v
    end
  ) edges;
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        if dist.(i).(k) < infinity && dist.(k).(j) < infinity then begin
          let via = dist.(i).(k) + dist.(k).(j) in
          if via < dist.(i).(j) then begin
            dist.(i).(j) <- via;
            next.(i).(j) <- next.(i).(k)
          end
        end
      done
    done
  done;
  let neg_cycle = Array.exists (fun row -> row < 0) (Array.init n (fun i -> dist.(i).(i))) in
  (dist, next, neg_cycle)

let reconstruct next src dst =
  if next.(src).(dst) = -1 then None
  else begin
    let path = ref [src] in
    let v    = ref src in
    while !v <> dst do
      v := next.(!v).(dst);
      path := !v :: !path
    done;
    Some (List.rev !path)
  end

let () =
  let edges = [(0,1,3);(0,3,7);(1,0,8);(1,2,2);(2,0,5);(2,3,1);(3,0,2)] in
  let n = 4 in
  let (dist, next, nc) = floyd_warshall n edges in
  Printf.printf "Negative cycle: %b\n" nc;
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      if dist.(i).(j) >= infinity then
        Printf.printf "  %d->%d: INF\n" i j
      else begin
        let path_str = match reconstruct next i j with
          | None   -> "none"
          | Some p -> String.concat "->" (List.map string_of_int p)
        in
        Printf.printf "  %d->%d: %d  [%s]\n" i j dist.(i).(j) path_str
      end
    done
  done

Key Differences

All-pairs vs single-source: Floyd-Warshall is the only practical all-pairs algorithm; Rust programs that need all-pairs often run Dijkstra V times instead for sparse graphs.

Overflow prevention: Both languages divide the infinity sentinel by 2; Rust's i32::MAX/2 and OCaml's max_int/2 serve the same purpose.

Negative cycles: dist[v][v] < 0 after the algorithm indicates a negative cycle; both languages detect this the same way.

Transitive closure: Boolean Floyd-Warshall (with || instead of min) computes reachability; OCaml's Ocamlgraph.Fixpoint does this automatically for labeled graphs.

OCaml Approach

OCaml uses Array.make_matrix n n max_int with max_int/2 as the convention. The triple for-loop is identical. OCaml's min function and array mutation follow the same structure. For transitive closure, replace int with bool and min with ||. The Ocamlgraph library implements Floyd-Warshall as part of its path algorithms suite.

Full Source

#![allow(clippy::all)]
//! # Floyd-Warshall Algorithm

pub fn floyd_warshall(n: usize, edges: &[(usize, usize, i32)]) -> Vec<Vec<i32>> {
    let mut dist = vec![vec![i32::MAX / 2; n]; n];
    for i in 0..n {
        dist[i][i] = 0;
    }
    for &(u, v, w) in edges {
        dist[u][v] = w;
    }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    dist
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_floyd() {
        let edges = [(0, 1, 3), (0, 2, 8), (1, 2, 2), (2, 0, 5)];
        let dist = floyd_warshall(3, &edges);
        assert_eq!(dist[0][2], 5);
    }
}

(* Floyd-Warshall — all-pairs shortest paths O(V³) *)
let infinity = max_int / 2

let floyd_warshall n edges =
  let dist = Array.init n (fun i -> Array.init n (fun j ->
    if i = j then 0 else infinity
  )) in
  let next = Array.init n (fun _ -> Array.make n (-1)) in
  List.iter (fun (u, v, w) ->
    if w < dist.(u).(v) then begin
      dist.(u).(v) <- w;
      next.(u).(v) <- v
    end
  ) edges;
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        if dist.(i).(k) < infinity && dist.(k).(j) < infinity then begin
          let via = dist.(i).(k) + dist.(k).(j) in
          if via < dist.(i).(j) then begin
            dist.(i).(j) <- via;
            next.(i).(j) <- next.(i).(k)
          end
        end
      done
    done
  done;
  let neg_cycle = Array.exists (fun row -> row < 0) (Array.init n (fun i -> dist.(i).(i))) in
  (dist, next, neg_cycle)

let reconstruct next src dst =
  if next.(src).(dst) = -1 then None
  else begin
    let path = ref [src] in
    let v    = ref src in
    while !v <> dst do
      v := next.(!v).(dst);
      path := !v :: !path
    done;
    Some (List.rev !path)
  end

let () =
  let edges = [(0,1,3);(0,3,7);(1,0,8);(1,2,2);(2,0,5);(2,3,1);(3,0,2)] in
  let n = 4 in
  let (dist, next, nc) = floyd_warshall n edges in
  Printf.printf "Negative cycle: %b\n" nc;
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      if dist.(i).(j) >= infinity then
        Printf.printf "  %d->%d: INF\n" i j
      else begin
        let path_str = match reconstruct next i j with
          | None   -> "none"
          | Some p -> String.concat "->" (List.map string_of_int p)
        in
        Printf.printf "  %d->%d: %d  [%s]\n" i j dist.(i).(j) path_str
      end
    done
  done

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_floyd() {
        let edges = [(0, 1, 3), (0, 2, 8), (1, 2, 2), (2, 0, 5)];
        let dist = floyd_warshall(3, &edges);
        assert_eq!(dist[0][2], 5);
    }
}

Deep Comparison

OCaml vs Rust: Floyd Warshall

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement the boolean transitive closure variant: replace i32 with bool and use || and && instead of min/add.

Detect and report all negative cycles: after running Floyd-Warshall, find all vertices v where dist[v][v] < 0 and trace which cycle they belong to.

Use Floyd-Warshall to compute "six degrees of separation" in a social network: load a friend graph and find the average shortest path length between all pairs.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust