Dijkstra's Shortest Path
Graph AlgorithmsPriority QueuesFunctional Data Structures
Tutorial Video
Text description (accessibility)
This video demonstrates the "Dijkstra's Shortest Path" functional Rust example. Difficulty level: Advanced. Key concepts covered: Graph Algorithms, Priority Queues, Functional Data Structures. Given a weighted directed graph and a source node, find the shortest distance from the source to every reachable node. Key difference from OCaml: 1. **Mutability:** OCaml's `IntMap` is truly immutable (new map per update). Rust's `HashMap` is mutated in place but owned — Rust's type system prevents the bugs that mutation usually causes.
Tutorial
The Problem
Given a weighted directed graph and a source node, find the shortest distance from the source to every reachable node. This is Dijkstra's algorithm — one of the most important algorithms in computer science — implemented with functional programming patterns in both OCaml and Rust.
🎯 Learning Outcomes
🦀 The Rust Way
Rust uses BinaryHeap (reversed via custom Ord for min-heap behavior) and HashMap for distances. While the maps are technically mutable, the algorithm follows a functional accumulation pattern:
while let Some(State { cost, node }) = heap.pop() {
if cost > *dist.get(&node).unwrap_or(&u64::MAX) {
continue; // skip stale — functional "already visited"
}
// fold over neighbors...
}
Key features:
Code Example
#[derive(Clone, Eq, PartialEq)]
struct State { cost: u64, node: usize }
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
// Reverse ordering: BinaryHeap is max-heap, we want min-heap
other.cost.cmp(&self.cost).then_with(|| self.node.cmp(&other.node))
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}
pub fn dijkstra(graph: &Graph, source: usize) -> HashMap<usize, u64> {
let mut dist = HashMap::new();
let mut heap = BinaryHeap::new();
dist.insert(source, 0);
heap.push(State { cost: 0, node: source });
while let Some(State { cost, node }) = heap.pop() {
if cost > *dist.get(&node).unwrap_or(&u64::MAX) { continue; }
if let Some(edges) = graph.get(&node) {
for edge in edges {
let new_dist = cost + edge.weight;
if new_dist < *dist.get(&edge.to).unwrap_or(&u64::MAX) {
dist.insert(edge.to, new_dist);
heap.push(State { cost: new_dist, node: edge.to });
}
}
}
}
dist
}Key Differences
IntMap is truly immutable (new map per update). Rust's HashMap is mutated in place but owned — Rust's type system prevents the bugs that mutation usually causes.BinaryHeap (O(log n) insert/pop) but needs a wrapper type with reversed Ord since Rust only provides max-heap.OCaml Approach
OCaml uses a purely functional priority queue (sorted association list) and immutable IntMap for distances. The algorithm is expressed as a recursive loop with pattern matching:
let rec loop pq dist =
match PQ.pop pq with
| None -> dist
| Some ((d, u), pq') ->
(* fold over neighbors, accumulate new distances *)
Key features:
IntMap.addFull Source
#![allow(clippy::all)]
//! Dijkstra's Shortest Path — Functional Rust with BinaryHeap and immutable-style updates.
//!
//! Demonstrates how Rust's ownership model naturally prevents the aliasing bugs
//! that plague mutable graph algorithms in imperative languages.
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap};
/// A weighted edge in the graph.
#[derive(Clone, Debug)]
pub struct Edge {
pub to: usize,
pub weight: u64,
}
/// Wrapper for BinaryHeap to get min-heap behavior (Rust's BinaryHeap is max-heap).
#[derive(Clone, Eq, PartialEq)]
struct State {
cost: u64,
node: usize,
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
// Reverse ordering for min-heap
other
.cost
.cmp(&self.cost)
.then_with(|| self.node.cmp(&other.node))
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
/// Adjacency list representation of a weighted directed graph.
pub type Graph = HashMap<usize, Vec<Edge>>;
/// Build a graph from a list of (from, to, weight) tuples.
/// Functional style: fold over edges to construct the adjacency map.
pub fn build_graph(edges: &[(usize, usize, u64)]) -> Graph {
edges
.iter()
.fold(HashMap::new(), |mut graph, &(from, to, weight)| {
graph.entry(from).or_default().push(Edge { to, weight });
graph
})
}
/// Compute shortest distances from `source` to all reachable nodes.
///
/// Returns a HashMap<usize, u64> mapping each node to its shortest distance.
/// Unreachable nodes are absent from the result.
///
/// # Functional patterns used:
/// - **Fold-like iteration** over neighbors (functional accumulation)
/// - **Immutable result map** built incrementally
/// - **Pattern matching** on heap state
pub fn dijkstra(graph: &Graph, source: usize) -> HashMap<usize, u64> {
let mut dist: HashMap<usize, u64> = HashMap::new();
let mut heap = BinaryHeap::new();
dist.insert(source, 0);
heap.push(State {
cost: 0,
node: source,
});
while let Some(State { cost, node }) = heap.pop() {
// Skip stale entries — functional equivalent of "already visited"
if cost > *dist.get(&node).unwrap_or(&u64::MAX) {
continue;
}
// Fold over neighbors: accumulate new distances
if let Some(edges) = graph.get(&node) {
for edge in edges {
let new_dist = cost + edge.weight;
let current = *dist.get(&edge.to).unwrap_or(&u64::MAX);
if new_dist < current {
dist.insert(edge.to, new_dist);
heap.push(State {
cost: new_dist,
node: edge.to,
});
}
}
}
}
dist
}
/// Reconstruct the shortest path from source to target.
/// Uses functional backtracking through the distance map.
pub fn shortest_path(graph: &Graph, source: usize, target: usize) -> Option<(u64, Vec<usize>)> {
let dist = dijkstra(graph, source);
let total_dist = *dist.get(&target)?;
// Backtrack from target to source
let mut path = vec![target];
let mut current = target;
while current != source {
let prev = graph
.iter()
.flat_map(|(&from, edges)| {
edges
.iter()
.filter(move |e| e.to == current)
.map(move |e| (from, e.weight))
})
.filter(|&(from, weight)| {
dist.get(&from)
.is_some_and(|&d| d + weight == *dist.get(¤t).unwrap())
})
.map(|(from, _)| from)
.next()?;
path.push(prev);
current = prev;
}
path.reverse();
Some((total_dist, path))
}
#[cfg(test)]
mod tests {
use super::*;
fn sample_graph() -> Graph {
// 0 --1-- 1 --2-- 2
// | |
// 4 1
// | |
// 3 ------3----- 4
build_graph(&[(0, 1, 1), (1, 2, 2), (0, 3, 4), (2, 4, 1), (3, 4, 3)])
}
#[test]
fn test_source_distance_is_zero() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&0], 0);
}
#[test]
fn test_direct_neighbor() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&1], 1);
}
#[test]
fn test_two_hops() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&2], 3); // 0->1 (1) + 1->2 (2) = 3
}
#[test]
fn test_shortest_via_longer_path() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&3], 4); // direct 0->3 = 4
}
#[test]
fn test_shortest_to_distant_node() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&4], 4); // 0->1->2->4 = 1+2+1 = 4 (shorter than 0->3->4 = 4+3 = 7)
}
#[test]
fn test_unreachable_node() {
let g = build_graph(&[(0, 1, 1)]);
let dist = dijkstra(&g, 0);
assert!(!dist.contains_key(&99));
}
#[test]
fn test_single_node_graph() {
let g = build_graph(&[]);
let dist = dijkstra(&g, 0);
assert_eq!(dist[&0], 0);
assert_eq!(dist.len(), 1);
}
#[test]
fn test_shortest_path_reconstruction() {
let g = sample_graph();
let (cost, path) = shortest_path(&g, 0, 4).unwrap();
assert_eq!(cost, 4);
assert_eq!(path, vec![0, 1, 2, 4]);
}
#[test]
fn test_path_to_self() {
let g = sample_graph();
let (cost, path) = shortest_path(&g, 0, 0).unwrap();
assert_eq!(cost, 0);
assert_eq!(path, vec![0]);
}
#[test]
fn test_empty_graph_isolation() {
let g = build_graph(&[]);
let result = shortest_path(&g, 0, 5);
assert!(result.is_none());
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
fn sample_graph() -> Graph {
// 0 --1-- 1 --2-- 2
// | |
// 4 1
// | |
// 3 ------3----- 4
build_graph(&[(0, 1, 1), (1, 2, 2), (0, 3, 4), (2, 4, 1), (3, 4, 3)])
}
#[test]
fn test_source_distance_is_zero() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&0], 0);
}
#[test]
fn test_direct_neighbor() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&1], 1);
}
#[test]
fn test_two_hops() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&2], 3); // 0->1 (1) + 1->2 (2) = 3
}
#[test]
fn test_shortest_via_longer_path() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&3], 4); // direct 0->3 = 4
}
#[test]
fn test_shortest_to_distant_node() {
let g = sample_graph();
let dist = dijkstra(&g, 0);
assert_eq!(dist[&4], 4); // 0->1->2->4 = 1+2+1 = 4 (shorter than 0->3->4 = 4+3 = 7)
}
#[test]
fn test_unreachable_node() {
let g = build_graph(&[(0, 1, 1)]);
let dist = dijkstra(&g, 0);
assert!(!dist.contains_key(&99));
}
#[test]
fn test_single_node_graph() {
let g = build_graph(&[]);
let dist = dijkstra(&g, 0);
assert_eq!(dist[&0], 0);
assert_eq!(dist.len(), 1);
}
#[test]
fn test_shortest_path_reconstruction() {
let g = sample_graph();
let (cost, path) = shortest_path(&g, 0, 4).unwrap();
assert_eq!(cost, 4);
assert_eq!(path, vec![0, 1, 2, 4]);
}
#[test]
fn test_path_to_self() {
let g = sample_graph();
let (cost, path) = shortest_path(&g, 0, 0).unwrap();
assert_eq!(cost, 0);
assert_eq!(path, vec![0]);
}
#[test]
fn test_empty_graph_isolation() {
let g = build_graph(&[]);
let result = shortest_path(&g, 0, 5);
assert!(result.is_none());
}
}Deep Comparison
OCaml vs Rust: Dijkstra's Shortest Path
Side-by-Side Code
OCaml
(* Priority queue as sorted association list — purely functional *)
module PQ = struct
type t = (int * int) list
let insert dist node pq =
let rec go = function
| [] -> [(dist, node)]
| ((d, _) as x) :: rest ->
if dist <= d then (dist, node) :: x :: rest
else x :: go rest
in go pq
let pop = function
| [] -> None
| (d, n) :: rest -> Some ((d, n), rest)
end
let dijkstra graph source =
let dist = IntMap.singleton source 0 in
let pq = PQ.insert 0 source PQ.empty in
let rec loop pq dist =
match PQ.pop pq with
| None -> dist
| Some ((d, u), pq') ->
let current_dist = try IntMap.find u dist with Not_found -> max_int in
if d > current_dist then loop pq' dist
else
let neighbors = try IntMap.find u graph with Not_found -> [] in
let pq'', dist' =
List.fold_left (fun (pq_acc, dist_acc) (v, w) ->
let new_dist = d + w in
let old_dist = try IntMap.find v dist_acc with Not_found -> max_int in
if new_dist < old_dist then
(PQ.insert new_dist v pq_acc, IntMap.add v new_dist dist_acc)
else (pq_acc, dist_acc)
) (pq', dist) neighbors
in loop pq'' dist'
in loop pq dist
Rust (idiomatic — BinaryHeap min-heap via reversed Ord)
#[derive(Clone, Eq, PartialEq)]
struct State { cost: u64, node: usize }
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
// Reverse ordering: BinaryHeap is max-heap, we want min-heap
other.cost.cmp(&self.cost).then_with(|| self.node.cmp(&other.node))
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}
pub fn dijkstra(graph: &Graph, source: usize) -> HashMap<usize, u64> {
let mut dist = HashMap::new();
let mut heap = BinaryHeap::new();
dist.insert(source, 0);
heap.push(State { cost: 0, node: source });
while let Some(State { cost, node }) = heap.pop() {
if cost > *dist.get(&node).unwrap_or(&u64::MAX) { continue; }
if let Some(edges) = graph.get(&node) {
for edge in edges {
let new_dist = cost + edge.weight;
if new_dist < *dist.get(&edge.to).unwrap_or(&u64::MAX) {
dist.insert(edge.to, new_dist);
heap.push(State { cost: new_dist, node: edge.to });
}
}
}
}
dist
}
Rust (functional graph construction — fold over edge list)
pub fn build_graph(edges: &[(usize, usize, u64)]) -> Graph {
edges.iter().fold(HashMap::new(), |mut graph, &(from, to, weight)| {
graph.entry(from).or_default().push(Edge { to, weight });
graph
})
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Distance map type | int IntMap.t | HashMap<usize, u64> |
| Priority queue | (int * int) list (sorted) | BinaryHeap<State> |
| Graph type | (int * int) list IntMap.t | HashMap<usize, Vec<Edge>> |
| Dijkstra signature | graph -> int -> int IntMap.t | fn dijkstra(graph: &Graph, source: usize) -> HashMap<usize, u64> |
| Optional result | 'a option | Option<T> |
| Fold accumulator | ('a * 'b) tuple | (pq_acc, dist_acc) destructured |
Key Insights
BinaryHeap (O(log n)), but since Rust only provides max-heap, a custom Ord implementation reverses the comparison to achieve min-heap behavior. This is a classic Rust idiom: newtype + reversed Ord.IntMap.add produces a new map each step — true immutability via structural sharing. Rust's HashMap is mutated in-place, but Rust's ownership model ensures no aliased mutable references exist, providing the same safety guarantees without the allocation cost.d > current_dist via pattern match; Rust checks cost > dist[node] in the while let loop. The functional insight: lazy deletion is valid because we only commit a distance when it's minimal.fold_left vs Iterator Chains:** OCaml's List.fold_left explicitly threads (pq_acc, dist_acc) as a tuple through each neighbor. Rust expresses the same accumulation as a for loop over edges mutating dist and heap — idiomatic Rust prefers direct mutation of owned data over tuple threading when the data is already exclusively owned.shortest_path using an iterator chain with .flat_map, .filter, .map, .next() to backtrack through the distance map — demonstrating how Rust iterator combinators replace OCaml's recursive list comprehensions for search problems.When to Use Each Style
Use idiomatic Rust (BinaryHeap + HashMap): When performance matters — this is O((V + E) log V) with low constant factors, no GC pauses, and no allocations per map update.
Use the OCaml purely functional style: When you want proof-friendly code or need to checkpoint algorithm state (the immutable map is a snapshot of distances at each step, enabling backtracking or parallel exploration without copying).
Exercises
im::HashMap (persistent data structure crate)