800. Floyd-Warshall: All-Pairs Shortest Paths

Difficulty: 4 Level: Advanced Compute shortest paths between every pair of nodes in O(V³) — with path reconstruction via a `next` matrix and negative-cycle detection.

The Problem This Solves

When you need distances between all pairs of nodes — not just from one source — Floyd-Warshall is the right tool. Network latency matrices, road distance tables, transitive closure of reachability, and "six degrees of separation" style social network analysis all need all-pairs distances. Floyd-Warshall is simpler to implement than running Dijkstra V times (especially when negative edges are present), and for dense graphs where E ≈ V², it's asymptotically comparable. The `next` matrix variant makes path reconstruction O(path length) after O(V³) preprocessing — extremely useful when you're building a routing table that will be queried many times.

The Intuition

Ask: "does routing through node k improve the path from i to j?" Do this for every k from 0 to V-1. After considering all intermediate nodes, `dist[i][j]` holds the shortest path. This is the "intermediate node induction" insight: after the outer loop over k, `dist[i][j]` is the shortest path that only uses nodes 0..=k as intermediates. The diagonal check `dist[i][i] < 0` after the main loop reveals negative cycles. OCaml implements this with three nested loops on a 2D array; Rust uses exactly the same structure with `Vec<Vec<i64>>`.

How It Works in Rust

const INF: i64 = i64::MAX / 2;

// O(V³) time, O(V²) space
fn floyd_warshall(
 n: usize,
 edges: &[(usize, usize, i64)],
) -> (Vec<Vec<i64>>, Vec<Vec<Option<usize>>>, bool) {
 let mut dist = vec![vec![INF; n]; n];
 let mut next: Vec<Vec<Option<usize>>> = vec![vec![None; n]; n];

 for i in 0..n { dist[i][i] = 0; }
 for &(u, v, w) in edges {
     if w < dist[u][v] {
         dist[u][v] = w;
         next[u][v] = Some(v);
     }
 }

 // Main loop: try routing through each intermediate node k
 for k in 0..n {
     for i in 0..n {
         for j in 0..n {
             if dist[i][k] < INF && dist[k][j] < INF {
                 let via = dist[i][k] + dist[k][j];
                 if via < dist[i][j] {
                     dist[i][j] = via;
                     next[i][j] = next[i][k];  // route through k
                 }
             }
         }
     }
 }

 // Negative cycle: any node with negative self-distance
 let neg_cycle = (0..n).any(|i| dist[i][i] < 0);
 (dist, next, neg_cycle)
}

// Path reconstruction: follow next[src][dst] until we arrive
fn reconstruct(next: &Vec<Vec<Option<usize>>>, src: usize, dst: usize) -> Option<Vec<usize>> {
 if next[src][dst].is_none() { return None; }
 let mut path = vec![src];
 let mut v = src;
 while v != dst { v = next[v][dst]?; path.push(v); }
 Some(path)
}

The `next[i][j] = next[i][k]` update in the reconstruction matrix is subtle: when you route i→j through k, the first hop from i is still `next[i][k]` — because the full path from k to j is already encoded in the `next` matrix.

What This Unlocks

Network latency tables: precompute latency between all datacenter pairs for SLA routing decisions; rebuild when topology changes.
Transitive closure: set all edge weights to 1, run Floyd-Warshall, then `reachable[i][j] = dist[i][j] < INF`. Simpler than DFS/BFS for static dense graphs.
Social network analysis: "degrees of separation" between all user pairs, or finding the node that minimises average distance to all others (graph centre).

Key Differences

Concept	OCaml	Rust
2D matrix	`Array.make_matrix n n inf`	`vec![vec![INF; n]; n]`
`next` matrix	`int option array array`	`Vec<Vec<Option<usize>>>`
Loop order	`for k`, `for i`, `for j`	Identical — order is critical
Negative cycle	Check diagonal after loop	`.any(	i	dist[i][i] < 0)`
Path reconstruction	Recursive via `next`	Iterative `while v != dst` with `?` propagation

// Floyd-Warshall — all-pairs shortest paths O(V³)
const INF: i64 = i64::MAX / 2;

fn floyd_warshall(n: usize, edges: &[(usize, usize, i64)]) -> (Vec<Vec<i64>>, Vec<Vec<Option<usize>>>, bool) {
    let mut dist = vec![vec![INF; n]; n];
    let mut next: Vec<Vec<Option<usize>>> = vec![vec![None; n]; n];

    for i in 0..n { dist[i][i] = 0; }
    for &(u, v, w) in edges {
        if w < dist[u][v] {
            dist[u][v] = w;
            next[u][v] = Some(v);
        }
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] < INF && dist[k][j] < INF {
                    let via = dist[i][k] + dist[k][j];
                    if via < dist[i][j] {
                        dist[i][j] = via;
                        next[i][j] = next[i][k];
                    }
                }
            }
        }
    }

    let neg_cycle = (0..n).any(|i| dist[i][i] < 0);
    (dist, next, neg_cycle)
}

fn reconstruct(next: &Vec<Vec<Option<usize>>>, src: usize, dst: usize) -> Option<Vec<usize>> {
    if next[src][dst].is_none() { return None; }
    let mut path = vec![src];
    let mut v = src;
    while v != dst {
        v = next[v][dst]?;
        path.push(v);
    }
    Some(path)
}

fn main() {
    let edges = vec![(0,1,3i64),(0,3,7),(1,0,8),(1,2,2),(2,0,5),(2,3,1),(3,0,2)];
    let n = 4;
    let (dist, next, nc) = floyd_warshall(n, &edges);
    println!("Negative cycle: {nc}");
    for i in 0..n {
        for j in 0..n {
            if dist[i][j] >= INF {
                println!("  {i}->{j}: INF");
            } else {
                println!("  {i}->{j}: {}  {:?}", dist[i][j], reconstruct(&next, i, j));
            }
        }
    }
}

(* 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