1170 Advanced

Dijkstra's Shortest Path — Priority Queue

Functional Programming

Tutorial

The Problem

Find the shortest distance from a start node to every reachable node in a weighted directed graph. Uses Dijkstra's greedy algorithm driven by a priority queue that always processes the cheapest unvisited node first.

🎯 Learning Outcomes

• How BinaryHeap<(Reverse<u32>, String)> replaces OCaml's ordered Set.Make as a min-heap

• How BTreeMap replaces OCaml's Map.Make(String) for an ordered, functional distance map

• Pattern for "lazy deletion" of stale heap entries instead of a decrease-key operation

• How OCaml's recursive go pq dist translates to either an iterative loop or a recursive Rust function

🦀 The Rust Way

The idiomatic solution wraps BinaryHeap (a max-heap) with std::cmp::Reverse to invert ordering, giving an O(log n) min-heap. Because Rust's heap has no decrease-key, stale entries are left in place and skipped when popped (the "lazy deletion" pattern). A BTreeMap stores distances, matching OCaml's ordered string map.

Code Example

pub fn dijkstra(graph: &Graph, start: &str) -> BTreeMap<String, u32> {
    let mut dist: BTreeMap<String, u32> = BTreeMap::new();
    dist.insert(start.to_owned(), 0);

    let mut heap: BinaryHeap<(Reverse<u32>, String)> = BinaryHeap::new();
    heap.push((Reverse(0), start.to_owned()));

    while let Some((Reverse(d), u)) = heap.pop() {
        if dist.get(&u).is_some_and(|&best| d > best) {
            continue; // stale entry — lazy deletion
        }
        let neighbors = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]);
        for (v, w) in neighbors {
            let alt = d + w;
            let current = dist.get(v).copied().unwrap_or(u32::MAX);
            if alt < current {
                dist.insert(v.clone(), alt);
                heap.push((Reverse(alt), v.clone()));
            }
        }
    }
    dist
}

module PQ = Set.Make(struct
  type t = int * string
  let compare (d1,n1) (d2,n2) = compare (d1,n1) (d2,n2)
end)
module SMap = Map.Make(String)

let dijkstra graph start =
  let dist = SMap.singleton start 0 in
  let pq = PQ.singleton (0, start) in
  let rec go pq dist =
    if PQ.is_empty pq then dist
    else
      let (d, u) = PQ.min_elt pq in
      let pq = PQ.remove (d, u) pq in
      let neighbors = try SMap.find u graph with Not_found -> [] in
      let dist, pq = List.fold_left (fun (dist, pq) (v, w) ->
        let alt = d + w in
        let current = try SMap.find v dist with Not_found -> max_int in
        if alt < current then
          (SMap.add v alt dist, PQ.add (alt, v) pq)
        else (dist, pq)
      ) (dist, pq) neighbors in
      go pq dist
  in go pq dist

Key Differences

Priority queue type: OCaml uses an immutable Set.Make (balanced BST);

Rust uses a mutable BinaryHeap with Reverse for min semantics.

Decrease-key: OCaml's set supports cheap removal of any element;

Rust's heap does not, so stale entries accumulate and are filtered on pop.

Immutability: OCaml's go receives new map/set values each call;

Rust's idiomatic version mutates dist and heap in a while let loop.

Recursive style: The recursive Rust version uses BTreeMap<(u32,String),()>

as a functional ordered set, closely mirroring the OCaml structure.

OCaml Approach

OCaml builds a sorted set (Set.Make) keyed on (dist, node) pairs to act as a priority queue — min_elt extracts the cheapest entry in O(log n), and the set is immutable so each step returns a new version. A recursive inner function go threads both the queue and the distance map as pure values.

Full Source

//! Example 1170: Dijkstra's Shortest Path — Priority Queue
//!
//! Demonstrates Dijkstra's algorithm using a binary heap (min-heap via `Reverse`)
//! and BTreeMap, mirroring the OCaml functional priority queue approach.

use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap};

/// Type alias: adjacency list graph with string node names and integer weights.
pub type Graph = BTreeMap<String, Vec<(String, u32)>>;

/// Solution 1: Idiomatic Rust — BinaryHeap with Reverse for min-heap behaviour.
///
/// Returns a map from node name to shortest distance from `start`.
/// Nodes unreachable from `start` are absent from the result.
pub fn dijkstra(graph: &Graph, start: &str) -> BTreeMap<String, u32> {
    // dist maps node -> best known distance
    let mut dist: BTreeMap<String, u32> = BTreeMap::new();
    dist.insert(start.to_owned(), 0);

    // BinaryHeap is a max-heap; wrap in Reverse to get min-heap on distance.
    // Tuple ordering: (Reverse(dist), node)
    let mut heap: BinaryHeap<(Reverse<u32>, String)> = BinaryHeap::new();
    heap.push((Reverse(0), start.to_owned()));

    while let Some((Reverse(d), u)) = heap.pop() {
        // If we've already found a better path, skip this stale entry.
        if dist.get(&u).is_some_and(|&best| d > best) {
            continue;
        }

        let neighbors = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]);
        for (v, w) in neighbors {
            let alt = d + w;
            let current = dist.get(v).copied().unwrap_or(u32::MAX);
            if alt < current {
                dist.insert(v.clone(), alt);
                heap.push((Reverse(alt), v.clone()));
            }
        }
    }

    dist
}

/// Solution 2: Functional/recursive — mirrors the OCaml `go pq dist` tail recursion.
///
/// Uses a sorted `BTreeMap` as a functional priority queue (keyed by `(dist, node)`),
/// matching OCaml's `Set.Make` approach where `min_elt` gives the cheapest entry.
pub fn dijkstra_recursive(graph: &Graph, start: &str) -> BTreeMap<String, u32> {
    let mut dist = BTreeMap::new();
    dist.insert(start.to_owned(), 0u32);

    // pq: BTreeMap<(dist, node), ()> — ordered so first key is cheapest.
    let mut pq: BTreeMap<(u32, String), ()> = BTreeMap::new();
    pq.insert((0, start.to_owned()), ());

    go(graph, pq, dist)
}

/// Recursive driver that processes the priority queue functionally.
fn go(
    graph: &Graph,
    mut pq: BTreeMap<(u32, String), ()>,
    dist: BTreeMap<String, u32>,
) -> BTreeMap<String, u32> {
    // Base case: empty queue → done
    let Some(((d, u), _)) = pq.pop_first() else {
        return dist;
    };

    // Stale entry guard
    if dist.get(&u).is_some_and(|&best| d > best) {
        return go(graph, pq, dist);
    }

    let neighbors = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]);

    // Fold over neighbours — mirrors OCaml's List.fold_left
    let (dist, pq) = neighbors
        .iter()
        .fold((dist, pq), |(mut d_map, mut q), (v, w)| {
            let alt = d + w;
            let current = d_map.get(v).copied().unwrap_or(u32::MAX);
            if alt < current {
                d_map.insert(v.clone(), alt);
                q.insert((alt, v.clone()), ());
            }
            (d_map, q)
        });

    go(graph, pq, dist)
}

// ---------------------------------------------------------------------------
// Helpers for building graphs in tests
// ---------------------------------------------------------------------------

/// Convenience builder: constructs a `Graph` from a slice of `(node, neighbours)`.
pub fn build_graph(edges: &[(&str, &[(&str, u32)])]) -> Graph {
    edges
        .iter()
        .map(|(node, neighbours)| {
            let ns = neighbours
                .iter()
                .map(|(n, w)| ((*n).to_owned(), *w))
                .collect();
            ((*node).to_owned(), ns)
        })
        .collect()
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    fn sample_graph() -> Graph {
        build_graph(&[
            ("a", &[("b", 1), ("c", 4)]),
            ("b", &[("c", 2), ("d", 6)]),
            ("c", &[("d", 3)]),
            ("d", &[]),
        ])
    }

    #[test]
    fn test_dijkstra_distances_from_a() {
        let g = sample_graph();
        let dist = dijkstra(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3); // a→b→c = 1+2
        assert_eq!(dist["d"], 6); // a→b→c→d = 1+2+3
    }

    #[test]
    fn test_dijkstra_recursive_matches_idiomatic() {
        let g = sample_graph();
        let d1 = dijkstra(&g, "a");
        let d2 = dijkstra_recursive(&g, "a");
        assert_eq!(d1, d2);
    }

    #[test]
    fn test_start_node_distance_is_zero() {
        let g = sample_graph();
        for start in ["a", "b", "c", "d"] {
            let dist = dijkstra(&g, start);
            assert_eq!(dist[start], 0, "start node {start} must have distance 0");
        }
    }

    #[test]
    fn test_unreachable_node_absent() {
        // d has no outgoing edges, so starting from d only reaches d itself.
        let g = sample_graph();
        let dist = dijkstra(&g, "d");
        assert_eq!(dist.len(), 1);
        assert_eq!(dist["d"], 0);
    }

    #[test]
    fn test_single_node_graph() {
        let g = build_graph(&[("x", &[])]);
        let dist = dijkstra(&g, "x");
        assert_eq!(dist["x"], 0);
        assert_eq!(dist.len(), 1);
    }

    #[test]
    fn test_direct_vs_indirect_path() {
        // a→c direct costs 10; a→b→c costs 1+2=3 — algorithm must pick shorter.
        let g = build_graph(&[
            ("a", &[("b", 1), ("c", 10)]),
            ("b", &[("c", 2)]),
            ("c", &[]),
        ]);
        let dist = dijkstra(&g, "a");
        assert_eq!(dist["c"], 3);
    }
}

module PQ = Set.Make(struct
  type t = int * string
  let compare (d1,n1) (d2,n2) = compare (d1,n1) (d2,n2)
end)
module SMap = Map.Make(String)

let dijkstra graph start =
  let dist = SMap.singleton start 0 in
  let pq = PQ.singleton (0, start) in
  let rec go pq dist =
    if PQ.is_empty pq then dist
    else
      let (d, u) = PQ.min_elt pq in
      let pq = PQ.remove (d, u) pq in
      let neighbors = try SMap.find u graph with Not_found -> [] in
      let dist, pq = List.fold_left (fun (dist, pq) (v, w) ->
        let alt = d + w in
        let current = try SMap.find v dist with Not_found -> max_int in
        if alt < current then
          (SMap.add v alt dist, PQ.add (alt, v) pq)
        else (dist, pq)
      ) (dist, pq) neighbors in
      go pq dist
  in go pq dist

let () =
  let g = SMap.of_list [
    ("a",[("b",1);("c",4)]); ("b",[("c",2);("d",6)]);
    ("c",[("d",3)]); ("d",[])
  ] in
  let dist = dijkstra g "a" in
  SMap.iter (Printf.printf "%s: %d\n") dist

✓ Tests Rust test suite

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

    fn sample_graph() -> Graph {
        build_graph(&[
            ("a", &[("b", 1), ("c", 4)]),
            ("b", &[("c", 2), ("d", 6)]),
            ("c", &[("d", 3)]),
            ("d", &[]),
        ])
    }

    #[test]
    fn test_dijkstra_distances_from_a() {
        let g = sample_graph();
        let dist = dijkstra(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3); // a→b→c = 1+2
        assert_eq!(dist["d"], 6); // a→b→c→d = 1+2+3
    }

    #[test]
    fn test_dijkstra_recursive_matches_idiomatic() {
        let g = sample_graph();
        let d1 = dijkstra(&g, "a");
        let d2 = dijkstra_recursive(&g, "a");
        assert_eq!(d1, d2);
    }

    #[test]
    fn test_start_node_distance_is_zero() {
        let g = sample_graph();
        for start in ["a", "b", "c", "d"] {
            let dist = dijkstra(&g, start);
            assert_eq!(dist[start], 0, "start node {start} must have distance 0");
        }
    }

    #[test]
    fn test_unreachable_node_absent() {
        // d has no outgoing edges, so starting from d only reaches d itself.
        let g = sample_graph();
        let dist = dijkstra(&g, "d");
        assert_eq!(dist.len(), 1);
        assert_eq!(dist["d"], 0);
    }

    #[test]
    fn test_single_node_graph() {
        let g = build_graph(&[("x", &[])]);
        let dist = dijkstra(&g, "x");
        assert_eq!(dist["x"], 0);
        assert_eq!(dist.len(), 1);
    }

    #[test]
    fn test_direct_vs_indirect_path() {
        // a→c direct costs 10; a→b→c costs 1+2=3 — algorithm must pick shorter.
        let g = build_graph(&[
            ("a", &[("b", 1), ("c", 10)]),
            ("b", &[("c", 2)]),
            ("c", &[]),
        ]);
        let dist = dijkstra(&g, "a");
        assert_eq!(dist["c"], 3);
    }
}

Deep Comparison

OCaml vs Rust: Dijkstra's Shortest Path — Priority Queue

Side-by-Side Code

OCaml

module PQ = Set.Make(struct
  type t = int * string
  let compare (d1,n1) (d2,n2) = compare (d1,n1) (d2,n2)
end)
module SMap = Map.Make(String)

let dijkstra graph start =
  let dist = SMap.singleton start 0 in
  let pq = PQ.singleton (0, start) in
  let rec go pq dist =
    if PQ.is_empty pq then dist
    else
      let (d, u) = PQ.min_elt pq in
      let pq = PQ.remove (d, u) pq in
      let neighbors = try SMap.find u graph with Not_found -> [] in
      let dist, pq = List.fold_left (fun (dist, pq) (v, w) ->
        let alt = d + w in
        let current = try SMap.find v dist with Not_found -> max_int in
        if alt < current then
          (SMap.add v alt dist, PQ.add (alt, v) pq)
        else (dist, pq)
      ) (dist, pq) neighbors in
      go pq dist
  in go pq dist

Rust (idiomatic — BinaryHeap min-heap)

pub fn dijkstra(graph: &Graph, start: &str) -> BTreeMap<String, u32> {
    let mut dist: BTreeMap<String, u32> = BTreeMap::new();
    dist.insert(start.to_owned(), 0);

    let mut heap: BinaryHeap<(Reverse<u32>, String)> = BinaryHeap::new();
    heap.push((Reverse(0), start.to_owned()));

    while let Some((Reverse(d), u)) = heap.pop() {
        if dist.get(&u).is_some_and(|&best| d > best) {
            continue; // stale entry — lazy deletion
        }
        let neighbors = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]);
        for (v, w) in neighbors {
            let alt = d + w;
            let current = dist.get(v).copied().unwrap_or(u32::MAX);
            if alt < current {
                dist.insert(v.clone(), alt);
                heap.push((Reverse(alt), v.clone()));
            }
        }
    }
    dist
}

Rust (functional/recursive — mirrors OCaml `go pq dist`)

fn go(
    graph: &Graph,
    mut pq: BTreeMap<(u32, String), ()>,
    dist: BTreeMap<String, u32>,
) -> BTreeMap<String, u32> {
    let Some(((d, u), _)) = pq.pop_first() else {
        return dist; // base case: empty queue
    };
    if dist.get(&u).is_some_and(|&best| d > best) {
        return go(graph, pq, dist); // stale entry guard
    }
    let neighbors = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]);
    let (dist, pq) = neighbors
        .iter()
        .fold((dist, pq), |(mut d_map, mut q), (v, w)| {
            let alt = d + w;
            let current = d_map.get(v).copied().unwrap_or(u32::MAX);
            if alt < current {
                d_map.insert(v.clone(), alt);
                q.insert((alt, v.clone()), ());
            }
            (d_map, q)
        });
    go(graph, pq, dist)
}

Type Signatures

Concept	OCaml	Rust
Graph type	`(string * (string * int) list) SMap.t`	`BTreeMap<String, Vec<(String, u32)>>`
Priority queue	`PQ.t` (balanced BST via `Set.Make`)	`BinaryHeap<(Reverse<u32>, String)>`
Distance map	`int SMap.t`	`BTreeMap<String, u32>`
Function signature	`val dijkstra : ... -> string -> int SMap.t`	`fn dijkstra(graph: &Graph, start: &str) -> BTreeMap<String, u32>`
Missing key sentinel	`max_int` via exception	`u32::MAX` via `.unwrap_or(u32::MAX)`

Key Insights

Priority queue implementation: OCaml creates an ordered set with Set.Make

whose min_elt gives O(log n) minimum extraction. Rust uses BinaryHeap with std::cmp::Reverse to invert natural max-ordering into min semantics.

Decrease-key vs lazy deletion: OCaml's Set.Make supports remove of any

element, so old (dist, node) entries can be replaced when a shorter path is found. Rust's BinaryHeap has no decrease-key — stale entries accumulate and are skipped with a guard (d > best) when popped.

Immutability vs mutation: OCaml's go is purely functional — each call

receives fresh immutable values. The idiomatic Rust version mutates dist and heap inside a while let loop. The recursive Rust version passes owned values to approximate the OCaml style.

Error handling for missing keys: OCaml uses try SMap.find k m with Not_found -> default.

Rust uses .get(k).copied().unwrap_or(default) — a combinator that eliminates exceptions.

Fold over neighbours: Both OCaml and Rust use a left fold (List.fold_left /

.iter().fold(...)) to process neighbours functionally, threading (dist, pq) as the accumulator. This structural parallel is exact.

When to Use Each Style

Use idiomatic Rust (BinaryHeap) when: you want maximum performance — BinaryHeap has better cache behaviour and lower constant factors than a balanced BST.

Use recursive Rust (BTreeMap PQ) when: you want to demonstrate OCaml structural equivalence or compose the algorithm as a pure function without mutable state.

Open Source Repos

functional-rust

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

Rust