799 Advanced

799-bellman-ford — Bellman-Ford Algorithm

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "799-bellman-ford — Bellman-Ford Algorithm" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Bellman-Ford (1958/1965) finds shortest paths from a source to all vertices in a weighted graph, handling negative edge weights that Dijkstra cannot handle. Key difference from OCaml: 1. **Overflow guard**: Rust uses `i32::MAX` as infinity and guards with `!= i32::MAX` before adding; OCaml uses `max_int/2` to avoid overflow — both serve the same purpose.

Tutorial

The Problem

Bellman-Ford (1958/1965) finds shortest paths from a source to all vertices in a weighted graph, handling negative edge weights that Dijkstra cannot handle. It also detects negative-weight cycles. Used in network routing (RIP — Routing Information Protocol uses Bellman-Ford), currency arbitrage detection, and financial risk analysis. The O(VE) time complexity is slower than Dijkstra's O((V+E)logV) but handles a broader class of problems.

🎯 Learning Outcomes

• Implement Bellman-Ford with V-1 relaxation rounds over all edges

• Detect negative-weight cycles by checking if any edge can still be relaxed after V-1 rounds

• Understand why V-1 rounds suffice: any shortest path has at most V-1 edges

• Return None for graphs with negative cycles (shortest path is undefined)

• Compare with Dijkstra: Bellman-Ford is slower but handles negative weights

Code Example

#![allow(clippy::all)]
//! # Bellman-Ford Algorithm

pub fn bellman_ford(n: usize, edges: &[(usize, usize, i32)], src: usize) -> Option<Vec<i32>> {
    let mut dist = vec![i32::MAX; n];
    dist[src] = 0;
    for _ in 0..n - 1 {
        for &(u, v, w) in edges {
            if dist[u] != i32::MAX && dist[u] + w < dist[v] {
                dist[v] = dist[u] + w;
            }
        }
    }
    for &(u, v, w) in edges {
        if dist[u] != i32::MAX && dist[u] + w < dist[v] {
            return None; // Negative cycle
        }
    }
    Some(dist)
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_bellman() {
        let edges = [
            (0, 1, -1),
            (0, 2, 4),
            (1, 2, 3),
            (1, 3, 2),
            (1, 4, 2),
            (3, 2, 5),
            (3, 1, 1),
            (4, 3, -3),
        ];
        let dist = bellman_ford(5, &edges, 0).unwrap();
        // Shortest paths from 0: 0→1=-1, 0→1→4=1, 0→1→4→3=-2
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], -1);
        assert_eq!(dist[3], -2);
        assert_eq!(dist[4], 1);
    }
}

(* Bellman-Ford — O(V×E) with negative cycle detection *)
let infinity = max_int / 2

let bellman_ford n edges src =
  (* edges: (u, v, w) list *)
  let dist = Array.make n infinity in
  let prev = Array.make n (-1) in
  dist.(src) <- 0;
  (* V - 1 relaxation passes *)
  for _ = 1 to n - 1 do
    List.iter (fun (u, v, w) ->
      if dist.(u) < infinity && dist.(u) + w < dist.(v) then begin
        dist.(v) <- dist.(u) + w;
        prev.(v) <- u
      end
    ) edges
  done;
  (* Check for negative cycles *)
  let neg_cycle = List.exists (fun (u, v, w) ->
    dist.(u) < infinity && dist.(u) + w < dist.(v)
  ) edges in
  (dist, prev, neg_cycle)

let reconstruct prev dst =
  let path = ref [] in
  let v    = ref dst in
  while !v >= 0 do
    path := !v :: !path;
    v    := prev.(!v)
  done;
  !path

let () =
  (* Graph with negative edges but no negative cycle *)
  let edges = [
    (0, 1, -1); (0, 2,  4);
    (1, 2,  3); (1, 3,  2); (1, 4,  2);
    (3, 2,  5); (3, 1,  1);
    (4, 3, -3)
  ] in
  let n = 5 in
  let (dist, prev, nc) = bellman_ford n edges 0 in
  Printf.printf "Source: 0, Negative cycle: %b\n" nc;
  for i = 0 to n - 1 do
    if dist.(i) = infinity then
      Printf.printf "  0 -> %d: unreachable\n" i
    else begin
      let path = reconstruct prev i in
      Printf.printf "  0 -> %d: dist=%d, path=[%s]\n" i dist.(i)
        (String.concat "->" (List.map string_of_int path))
    end
  done;

  (* Graph with negative cycle *)
  let edges2 = [(0,1,1); (1,2,-1); (2,0,-1)] in
  let (_, _, nc2) = bellman_ford 3 edges2 0 in
  Printf.printf "\nNegative cycle test: %b\n" nc2

Key Differences

Overflow guard: Rust uses i32::MAX as infinity and guards with != i32::MAX before adding; OCaml uses max_int/2 to avoid overflow — both serve the same purpose.

Negative cycle: Both languages return an error/option on negative cycle detection, propagating the undefined result.

SPFA optimization: The "Shortest Path Faster Algorithm" uses a queue to skip relaxations that won't improve; this optimization applies equally to both languages.

Routing protocols: RIP uses Bellman-Ford with hop count as weight; BGP uses a path-vector variant; both are implemented in production network equipment software.

OCaml Approach

OCaml implements with Array.make n max_int and nested for loops. The negative cycle check adds one more relaxation attempt. Functional style using List.iter over edges is idiomatic. OCaml's Hashtbl can represent the adjacency list. The Int.max_int / 2 sentinel avoids overflow when adding edges to "infinity" values.

Full Source

#![allow(clippy::all)]
//! # Bellman-Ford Algorithm

pub fn bellman_ford(n: usize, edges: &[(usize, usize, i32)], src: usize) -> Option<Vec<i32>> {
    let mut dist = vec![i32::MAX; n];
    dist[src] = 0;
    for _ in 0..n - 1 {
        for &(u, v, w) in edges {
            if dist[u] != i32::MAX && dist[u] + w < dist[v] {
                dist[v] = dist[u] + w;
            }
        }
    }
    for &(u, v, w) in edges {
        if dist[u] != i32::MAX && dist[u] + w < dist[v] {
            return None; // Negative cycle
        }
    }
    Some(dist)
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_bellman() {
        let edges = [
            (0, 1, -1),
            (0, 2, 4),
            (1, 2, 3),
            (1, 3, 2),
            (1, 4, 2),
            (3, 2, 5),
            (3, 1, 1),
            (4, 3, -3),
        ];
        let dist = bellman_ford(5, &edges, 0).unwrap();
        // Shortest paths from 0: 0→1=-1, 0→1→4=1, 0→1→4→3=-2
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], -1);
        assert_eq!(dist[3], -2);
        assert_eq!(dist[4], 1);
    }
}

(* Bellman-Ford — O(V×E) with negative cycle detection *)
let infinity = max_int / 2

let bellman_ford n edges src =
  (* edges: (u, v, w) list *)
  let dist = Array.make n infinity in
  let prev = Array.make n (-1) in
  dist.(src) <- 0;
  (* V - 1 relaxation passes *)
  for _ = 1 to n - 1 do
    List.iter (fun (u, v, w) ->
      if dist.(u) < infinity && dist.(u) + w < dist.(v) then begin
        dist.(v) <- dist.(u) + w;
        prev.(v) <- u
      end
    ) edges
  done;
  (* Check for negative cycles *)
  let neg_cycle = List.exists (fun (u, v, w) ->
    dist.(u) < infinity && dist.(u) + w < dist.(v)
  ) edges in
  (dist, prev, neg_cycle)

let reconstruct prev dst =
  let path = ref [] in
  let v    = ref dst in
  while !v >= 0 do
    path := !v :: !path;
    v    := prev.(!v)
  done;
  !path

let () =
  (* Graph with negative edges but no negative cycle *)
  let edges = [
    (0, 1, -1); (0, 2,  4);
    (1, 2,  3); (1, 3,  2); (1, 4,  2);
    (3, 2,  5); (3, 1,  1);
    (4, 3, -3)
  ] in
  let n = 5 in
  let (dist, prev, nc) = bellman_ford n edges 0 in
  Printf.printf "Source: 0, Negative cycle: %b\n" nc;
  for i = 0 to n - 1 do
    if dist.(i) = infinity then
      Printf.printf "  0 -> %d: unreachable\n" i
    else begin
      let path = reconstruct prev i in
      Printf.printf "  0 -> %d: dist=%d, path=[%s]\n" i dist.(i)
        (String.concat "->" (List.map string_of_int path))
    end
  done;

  (* Graph with negative cycle *)
  let edges2 = [(0,1,1); (1,2,-1); (2,0,-1)] in
  let (_, _, nc2) = bellman_ford 3 edges2 0 in
  Printf.printf "\nNegative cycle test: %b\n" nc2

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_bellman() {
        let edges = [
            (0, 1, -1),
            (0, 2, 4),
            (1, 2, 3),
            (1, 3, 2),
            (1, 4, 2),
            (3, 2, 5),
            (3, 1, 1),
            (4, 3, -3),
        ];
        let dist = bellman_ford(5, &edges, 0).unwrap();
        // Shortest paths from 0: 0→1=-1, 0→1→4=1, 0→1→4→3=-2
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], -1);
        assert_eq!(dist[3], -2);
        assert_eq!(dist[4], 1);
    }
}

Deep Comparison

OCaml vs Rust: Bellman Ford

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 SPFA (Bellman-Ford with a queue): only relax edges from nodes whose distance was recently updated. Benchmark against naive Bellman-Ford on sparse graphs.

Add bellman_ford_path(n, edges, src, dst) -> Option<Vec<usize>> that reconstructs the shortest path from src to dst using a predecessor array.

Use Bellman-Ford to detect currency arbitrage: given exchange rates as a complete graph with log-weight edges, a negative cycle indicates an arbitrage opportunity.

Open Source Repos

functional-rust

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

Rust