380 Intermediate

380: Weighted Graph and Dijkstra's Algorithm

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "380: Weighted Graph and Dijkstra's Algorithm" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Edge weights model real costs: road distances, network latency, flight prices, pipeline capacities. Key difference from OCaml: 1. **Min

Tutorial

The Problem

Edge weights model real costs: road distances, network latency, flight prices, pipeline capacities. Edsger Dijkstra introduced his shortest-path algorithm in 1956 to find minimum-cost routes in graphs with non-negative weights. It runs in O((V + E) log V) with a binary heap and is the foundation of GPS routing, internet packet routing (OSPF protocol), game AI pathfinding, and transportation optimization.

Dijkstra's algorithm is implemented in every major programming language's standard library ecosystem and powers Google Maps, Cisco routers, and real-time strategy game unit movement.

🎯 Learning Outcomes

• Understand why Dijkstra's algorithm requires non-negative edge weights (negative edges require Bellman-Ford)

• Learn how a min-heap (priority queue) drives the greedy selection of the next closest vertex

• Understand the Reverse wrapper for converting Rust's max-heap BinaryHeap into a min-heap

• Learn path reconstruction via parent pointer arrays alongside distance arrays

• See how u64::MAX as infinity enables clean relaxation logic with saturating_add

Code Example

#![allow(clippy::all)]
//! Weighted Graph and Dijkstra's Algorithm
//!
//! Shortest paths with non-negative edge weights.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Dijkstra's shortest path algorithm
/// Returns distances from src to all vertices
pub fn dijkstra(adj: &[Vec<(usize, u64)>], n: usize, src: usize) -> Vec<u64> {
    let mut dist = vec![u64::MAX; n];
    dist[src] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0u64, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
            continue;
        }
        for &(v, w) in &adj[u] {
            let nd = dist[u].saturating_add(w);
            if nd < dist[v] {
                dist[v] = nd;
                heap.push(Reverse((nd, v)));
            }
        }
    }
    dist
}

/// Dijkstra with path reconstruction
pub fn dijkstra_with_path(
    adj: &[Vec<(usize, u64)>],
    n: usize,
    src: usize,
    dst: usize,
) -> (u64, Vec<usize>) {
    let mut dist = vec![u64::MAX; n];
    let mut prev = vec![usize::MAX; n];
    dist[src] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0u64, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
            continue;
        }
        if u == dst {
            break;
        }
        for &(v, w) in &adj[u] {
            let nd = dist[u].saturating_add(w);
            if nd < dist[v] {
                dist[v] = nd;
                prev[v] = u;
                heap.push(Reverse((nd, v)));
            }
        }
    }

    // Reconstruct path
    let mut path = Vec::new();
    if dist[dst] != u64::MAX {
        let mut cur = dst;
        while cur != usize::MAX {
            path.push(cur);
            cur = prev[cur];
        }
        path.reverse();
    }
    (dist[dst], path)
}

/// Bellman-Ford for graphs with negative weights
pub fn bellman_ford(edges: &[(usize, usize, i64)], n: usize, src: usize) -> Option<Vec<i64>> {
    let mut dist = vec![i64::MAX; n];
    dist[src] = 0;

    for _ in 0..n - 1 {
        for &(u, v, w) in edges {
            if dist[u] != i64::MAX && dist[u] + w < dist[v] {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative cycles
    for &(u, v, w) in edges {
        if dist[u] != i64::MAX && dist[u] + w < dist[v] {
            return None; // negative cycle
        }
    }
    Some(dist)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dijkstra() {
        let mut adj = vec![vec![]; 4];
        adj[0].push((1, 1u64));
        adj[0].push((2, 4));
        adj[1].push((2, 2));
        adj[1].push((3, 5));
        adj[2].push((3, 1));
        let dist = dijkstra(&adj, 4, 0);
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], 1);
        assert_eq!(dist[2], 3);
        assert_eq!(dist[3], 4);
    }

    #[test]
    fn test_unreachable() {
        let adj = vec![vec![(1, 1u64)], vec![], vec![]];
        let dist = dijkstra(&adj, 3, 0);
        assert_eq!(dist[2], u64::MAX);
    }

    #[test]
    fn test_path_reconstruction() {
        let mut adj = vec![vec![]; 4];
        adj[0].push((1, 1u64));
        adj[1].push((2, 1));
        adj[2].push((3, 1));
        let (dist, path) = dijkstra_with_path(&adj, 4, 0, 3);
        assert_eq!(dist, 3);
        assert_eq!(path, vec![0, 1, 2, 3]);
    }

    #[test]
    fn test_bellman_ford() {
        let edges = vec![(0, 1, 4i64), (0, 2, 5), (1, 2, -3), (2, 3, 4)];
        let dist = bellman_ford(&edges, 4, 0).unwrap();
        assert_eq!(dist[0], 0);
        assert_eq!(dist[2], 1); // 0->1->2: 4-3=1
    }

    #[test]
    fn test_negative_cycle() {
        let edges = vec![(0, 1, 1i64), (1, 2, -1), (2, 0, -1)];
        assert!(bellman_ford(&edges, 3, 0).is_none());
    }
}

(* Dijkstra's shortest path in OCaml *)
(* Priority queue via sorted list (simple but not optimal) *)

let dijkstra adj n src =
  let inf = max_int in
  let dist = Array.make n inf in
  let visited = Array.make n false in
  dist.(src) <- 0;
  let pq = ref [(0, src)] in
  while !pq <> [] do
    let (d, u) = List.hd !pq in
    pq := List.tl !pq;
    if not visited.(u) then begin
      visited.(u) <- true;
      List.iter (fun (v, w) ->
        if dist.(u) <> inf && dist.(u) + w < dist.(v) then begin
          dist.(v) <- dist.(u) + w;
          pq := List.sort compare ((dist.(v), v) :: !pq)
        end
      ) adj.(u)
    end
  done;
  dist

let () =
  let n = 5 in
  let adj = Array.make n [] in
  let edges = [(0,1,10);(0,2,3);(1,3,2);(2,1,4);(2,3,8);(2,4,2);(3,4,5);(4,3,7)] in
  List.iter (fun (u,v,w) -> adj.(u) <- (v,w) :: adj.(u)) edges;
  let dist = dijkstra adj n 0 in
  Printf.printf "Shortest distances from vertex 0:\n";
  Array.iteri (fun v d ->
    if d = max_int then Printf.printf "  to %d: inf\n" v
    else Printf.printf "  to %d: %d\n" v d
  ) dist

Key Differences

Min-heap: Rust wraps with Reverse to invert BinaryHeap ordering; OCaml priority queues natively support custom comparators or use (dist, vertex) tuple ordering directly.

Infinity representation: Rust uses u64::MAX with saturating_add; OCaml uses max_int or infinity (float) or a custom type distance = Inf | Finite of int.

Path reconstruction: Rust uses a Vec<usize> parent array indexed by vertex; OCaml uses a Hashtbl or Map mapping vertex to previous vertex.

Mutability: Rust's distance array is mut Vec<u64> updated in place; OCaml's functional approach would use a persistent map, which is slower but produces an immutable audit trail.

OCaml Approach

OCaml implements Dijkstra using a priority queue module (from the standard library or a third-party psq package). The functional approach tracks distances in a Map rather than a mutable array, creating a new map at each relaxation step. An imperative version uses Bigarray or Array for distances. OCaml's compare functions work with tuples directly for heap ordering.

Full Source

#![allow(clippy::all)]
//! Weighted Graph and Dijkstra's Algorithm
//!
//! Shortest paths with non-negative edge weights.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Dijkstra's shortest path algorithm
/// Returns distances from src to all vertices
pub fn dijkstra(adj: &[Vec<(usize, u64)>], n: usize, src: usize) -> Vec<u64> {
    let mut dist = vec![u64::MAX; n];
    dist[src] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0u64, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
            continue;
        }
        for &(v, w) in &adj[u] {
            let nd = dist[u].saturating_add(w);
            if nd < dist[v] {
                dist[v] = nd;
                heap.push(Reverse((nd, v)));
            }
        }
    }
    dist
}

/// Dijkstra with path reconstruction
pub fn dijkstra_with_path(
    adj: &[Vec<(usize, u64)>],
    n: usize,
    src: usize,
    dst: usize,
) -> (u64, Vec<usize>) {
    let mut dist = vec![u64::MAX; n];
    let mut prev = vec![usize::MAX; n];
    dist[src] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0u64, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
            continue;
        }
        if u == dst {
            break;
        }
        for &(v, w) in &adj[u] {
            let nd = dist[u].saturating_add(w);
            if nd < dist[v] {
                dist[v] = nd;
                prev[v] = u;
                heap.push(Reverse((nd, v)));
            }
        }
    }

    // Reconstruct path
    let mut path = Vec::new();
    if dist[dst] != u64::MAX {
        let mut cur = dst;
        while cur != usize::MAX {
            path.push(cur);
            cur = prev[cur];
        }
        path.reverse();
    }
    (dist[dst], path)
}

/// Bellman-Ford for graphs with negative weights
pub fn bellman_ford(edges: &[(usize, usize, i64)], n: usize, src: usize) -> Option<Vec<i64>> {
    let mut dist = vec![i64::MAX; n];
    dist[src] = 0;

    for _ in 0..n - 1 {
        for &(u, v, w) in edges {
            if dist[u] != i64::MAX && dist[u] + w < dist[v] {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative cycles
    for &(u, v, w) in edges {
        if dist[u] != i64::MAX && dist[u] + w < dist[v] {
            return None; // negative cycle
        }
    }
    Some(dist)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dijkstra() {
        let mut adj = vec![vec![]; 4];
        adj[0].push((1, 1u64));
        adj[0].push((2, 4));
        adj[1].push((2, 2));
        adj[1].push((3, 5));
        adj[2].push((3, 1));
        let dist = dijkstra(&adj, 4, 0);
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], 1);
        assert_eq!(dist[2], 3);
        assert_eq!(dist[3], 4);
    }

    #[test]
    fn test_unreachable() {
        let adj = vec![vec![(1, 1u64)], vec![], vec![]];
        let dist = dijkstra(&adj, 3, 0);
        assert_eq!(dist[2], u64::MAX);
    }

    #[test]
    fn test_path_reconstruction() {
        let mut adj = vec![vec![]; 4];
        adj[0].push((1, 1u64));
        adj[1].push((2, 1));
        adj[2].push((3, 1));
        let (dist, path) = dijkstra_with_path(&adj, 4, 0, 3);
        assert_eq!(dist, 3);
        assert_eq!(path, vec![0, 1, 2, 3]);
    }

    #[test]
    fn test_bellman_ford() {
        let edges = vec![(0, 1, 4i64), (0, 2, 5), (1, 2, -3), (2, 3, 4)];
        let dist = bellman_ford(&edges, 4, 0).unwrap();
        assert_eq!(dist[0], 0);
        assert_eq!(dist[2], 1); // 0->1->2: 4-3=1
    }

    #[test]
    fn test_negative_cycle() {
        let edges = vec![(0, 1, 1i64), (1, 2, -1), (2, 0, -1)];
        assert!(bellman_ford(&edges, 3, 0).is_none());
    }
}

(* Dijkstra's shortest path in OCaml *)
(* Priority queue via sorted list (simple but not optimal) *)

let dijkstra adj n src =
  let inf = max_int in
  let dist = Array.make n inf in
  let visited = Array.make n false in
  dist.(src) <- 0;
  let pq = ref [(0, src)] in
  while !pq <> [] do
    let (d, u) = List.hd !pq in
    pq := List.tl !pq;
    if not visited.(u) then begin
      visited.(u) <- true;
      List.iter (fun (v, w) ->
        if dist.(u) <> inf && dist.(u) + w < dist.(v) then begin
          dist.(v) <- dist.(u) + w;
          pq := List.sort compare ((dist.(v), v) :: !pq)
        end
      ) adj.(u)
    end
  done;
  dist

let () =
  let n = 5 in
  let adj = Array.make n [] in
  let edges = [(0,1,10);(0,2,3);(1,3,2);(2,1,4);(2,3,8);(2,4,2);(3,4,5);(4,3,7)] in
  List.iter (fun (u,v,w) -> adj.(u) <- (v,w) :: adj.(u)) edges;
  let dist = dijkstra adj n 0 in
  Printf.printf "Shortest distances from vertex 0:\n";
  Array.iteri (fun v d ->
    if d = max_int then Printf.printf "  to %d: inf\n" v
    else Printf.printf "  to %d: %d\n" v d
  ) dist

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dijkstra() {
        let mut adj = vec![vec![]; 4];
        adj[0].push((1, 1u64));
        adj[0].push((2, 4));
        adj[1].push((2, 2));
        adj[1].push((3, 5));
        adj[2].push((3, 1));
        let dist = dijkstra(&adj, 4, 0);
        assert_eq!(dist[0], 0);
        assert_eq!(dist[1], 1);
        assert_eq!(dist[2], 3);
        assert_eq!(dist[3], 4);
    }

    #[test]
    fn test_unreachable() {
        let adj = vec![vec![(1, 1u64)], vec![], vec![]];
        let dist = dijkstra(&adj, 3, 0);
        assert_eq!(dist[2], u64::MAX);
    }

    #[test]
    fn test_path_reconstruction() {
        let mut adj = vec![vec![]; 4];
        adj[0].push((1, 1u64));
        adj[1].push((2, 1));
        adj[2].push((3, 1));
        let (dist, path) = dijkstra_with_path(&adj, 4, 0, 3);
        assert_eq!(dist, 3);
        assert_eq!(path, vec![0, 1, 2, 3]);
    }

    #[test]
    fn test_bellman_ford() {
        let edges = vec![(0, 1, 4i64), (0, 2, 5), (1, 2, -3), (2, 3, 4)];
        let dist = bellman_ford(&edges, 4, 0).unwrap();
        assert_eq!(dist[0], 0);
        assert_eq!(dist[2], 1); // 0->1->2: 4-3=1
    }

    #[test]
    fn test_negative_cycle() {
        let edges = vec![(0, 1, 1i64), (1, 2, -1), (2, 0, -1)];
        assert!(bellman_ford(&edges, 3, 0).is_none());
    }
}

Deep Comparison

OCaml vs Rust: Dijkstra

Both use priority queue (binary heap) for efficiency.

Exercises

Bellman-Ford: Implement Bellman-Ford shortest paths which handles negative edge weights, and add cycle detection that identifies negative-weight cycles.

All-pairs shortest paths: Implement Floyd-Warshall for dense graphs, returning a 2D distance matrix, and compare runtime with running Dijkstra from every vertex.

*A search**: Extend Dijkstra with a heuristic function h(v) -> u64 that estimates remaining distance to goal, turning it into A* for grid-based pathfinding. Use Manhattan distance as the heuristic.

Open Source Repos

functional-rust

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

Rust