1110 Advanced

Dijkstra's Shortest Path — Priority Queue

GraphsAlgorithms

Tutorial Video

Text description (accessibility)

This video demonstrates the "Dijkstra's Shortest Path — Priority Queue" functional Rust example. Difficulty level: Advanced. Key concepts covered: Graphs, Algorithms. Find the shortest-path distance from a start node to every reachable node in a weighted directed graph, using Dijkstra's algorithm with a priority queue. Key difference from OCaml: 1. **Priority Queue:** OCaml `Set.Make` is a balanced BST — no duplicate `(d, node)` pairs allowed; set semantics enforce uniqueness. Rust `BinaryHeap` is a binary heap — duplicates are allowed, filtered lazily by checking `d > dist[u]`.

Tutorial

The Problem

Find the shortest-path distance from a start node to every reachable node in a weighted directed graph, using Dijkstra's algorithm with a priority queue.

🎯 Learning Outcomes

• How BinaryHeap<Reverse<T>> translates OCaml's Set.Make ordered-BST priority queue

• Why duplicate entries arise in heap-based Dijkstra and how to filter them idiomatically

• Using BTreeSet::pop_first() as a direct analog of OCaml's PQ.min_elt + PQ.remove

• How OCaml's try ... with Not_found -> default maps to Rust's .unwrap_or(default)

🦀 The Rust Way

The idiomatic Rust version uses BinaryHeap<Reverse<(i32, String)>> — a max-heap flipped to min-heap semantics via Reverse. Because BinaryHeap allows duplicate entries (unlike OCaml's Set), stale entries are filtered with a one-line check. The functional variant uses BTreeSet<(i32, String)> and BTreeMap, mirroring OCaml's sorted-set PQ and functional map, with an inner recursive go function.

Code Example

pub fn dijkstra(
    graph: &HashMap<String, Vec<(String, i32)>>,
    start: &str,
) -> HashMap<String, i32> {
    let mut dist: HashMap<String, i32> = HashMap::from([(start.to_string(), 0)]);
    let mut heap: BinaryHeap<Reverse<(i32, String)>> =
        BinaryHeap::from([Reverse((0, start.to_string()))]);

    while let Some(Reverse((d, u))) = heap.pop() {
        // stale-entry filter: replaces OCaml Set's no-duplicate guarantee
        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;
            if alt < dist.get(v).copied().unwrap_or(i32::MAX) {
                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: OCaml Set.Make is a balanced BST — no duplicate (d, node) pairs allowed; set semantics enforce uniqueness. Rust BinaryHeap is a binary heap — duplicates are allowed, filtered lazily by checking d > dist[u].

Min extraction: OCaml PQ.min_elt + PQ.remove → two calls. Rust BTreeSet::pop_first() atomically removes and returns the minimum in one call.

Not-found handling: OCaml try SMap.find v dist with Not_found -> max_int uses exception-based control flow. Rust .unwrap_or(i32::MAX) expresses the same default with pure Option combinators.

Tail recursion: OCaml's let rec go is tail-recursive and the compiler emits a loop. Rust's inner fn go has no guaranteed TCO — for large graphs the iterative dijkstra avoids stack overflow.

OCaml Approach

OCaml defines a custom-compared Set.Make module as a priority queue: because the set is ordered by (distance, node), PQ.min_elt always returns the cheapest unvisited node in O(log n). The distance map is a Map.Make(String). The algorithm is expressed as a tail-recursive let rec go pq dist accumulator — idiomatic functional style.

Full Source

#![allow(clippy::all)]
// 1110: Dijkstra's Shortest Path — Priority Queue
//
// OCaml uses `Set.Make` as a sorted priority queue (ordered BST of (dist, node) tuples)
// and `Map.Make(String)` as the distance map.
//
// Rust translates this to two variants:
//   1. Idiomatic: `BinaryHeap<Reverse<(i32, String)>>` + `HashMap` — fast, imperative
//   2. Functional: `BTreeSet<(i32, String)>` + `BTreeMap` — mirrors OCaml's ordered-set PQ
//
// Key OCaml→Rust translation:
//   - `PQ.min_elt` + `PQ.remove` → `BTreeSet::pop_first()` (stable since Rust 1.66)
//   - `try SMap.find v dist with Not_found -> max_int` → `.unwrap_or(i32::MAX)`
//   - `List.fold_left` over neighbors → `.iter().fold(...)`
//   - `let rec go pq dist = ...` → inner `fn go(...)` (no TCO guarantee in Rust)

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

/// Idiomatic Rust — BinaryHeap (min-heap via Reverse) + HashMap.
///
/// OCaml's `Set.Make` priority queue is a balanced BST; it deduplicates entries
/// automatically. Rust's `BinaryHeap` is a binary heap that allows duplicates.
/// We compensate with a stale-entry check: if the popped distance `d` is greater
/// than the best known `dist[u]`, the entry is outdated and we skip it.
///
/// Complexity: O((V + E) log V) — same asymptotic as the OCaml version.
pub fn dijkstra(graph: &HashMap<String, Vec<(String, i32)>>, start: &str) -> HashMap<String, i32> {
    let mut dist: HashMap<String, i32> = HashMap::from([(start.to_string(), 0)]);
    // Reverse turns the max-heap into a min-heap: smallest distance is popped first.
    let mut heap: BinaryHeap<Reverse<(i32, String)>> =
        BinaryHeap::from([Reverse((0, start.to_string()))]);

    while let Some(Reverse((d, u))) = heap.pop() {
        // OCaml's Set prevents stale entries; we skip them here instead.
        if dist.get(&u).is_some_and(|&best| d > best) {
            continue;
        }
        // OCaml: `try SMap.find u graph with Not_found -> []`
        let neighbors = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]);
        for (v, w) in neighbors {
            let alt = d + w;
            // OCaml: `try SMap.find v dist with Not_found -> max_int`
            if alt < dist.get(v).copied().unwrap_or(i32::MAX) {
                dist.insert(v.clone(), alt); // clone: need owned String for the map key
                heap.push(Reverse((alt, v.clone()))); // clone: heap takes ownership
            }
        }
    }
    dist
}

/// Functional / set-based — mirrors OCaml's `module PQ = Set.Make` approach.
///
/// Uses `BTreeSet<(i32, String)>` as an ordered priority queue (like OCaml's `Set.Make`)
/// and `BTreeMap<String, i32>` as the distance map (like OCaml's `Map.Make(String)`).
///
/// `pop_first()` atomically removes and returns the minimum element, directly
/// translating OCaml's `PQ.min_elt pq` + `PQ.remove (d, u) pq`.
///
/// The inner `go` mirrors OCaml's `let rec go pq dist = if PQ.is_empty pq then dist`.
///
/// Note: Rust lacks guaranteed tail-call optimisation. For large graphs, prefer
/// the iterative `dijkstra` above to avoid stack overflow.
pub fn dijkstra_functional(
    graph: &BTreeMap<String, Vec<(String, i32)>>,
    start: &str,
) -> BTreeMap<String, i32> {
    // Inner helper — mirrors `let rec go pq dist = ...` in OCaml.
    fn go(
        graph: &BTreeMap<String, Vec<(String, i32)>>,
        mut pq: BTreeSet<(i32, String)>,
        dist: BTreeMap<String, i32>,
    ) -> BTreeMap<String, i32> {
        // OCaml: `if PQ.is_empty pq then dist`
        let Some((d, u)) = pq.pop_first() else {
            return dist;
        };

        // OCaml: `let dist, pq = List.fold_left (...) (dist, pq) neighbors`
        let (dist, pq) = graph.get(&u).map(Vec::as_slice).unwrap_or(&[]).iter().fold(
            (dist, pq),
            |(mut dist, mut pq), (v, w)| {
                let alt = d + w;
                let current = dist.get(v).copied().unwrap_or(i32::MAX);
                if alt < current {
                    dist.insert(v.clone(), alt); // clone: BTreeMap needs owned key
                    pq.insert((alt, v.clone())); // clone: BTreeSet needs owned value
                }
                (dist, pq)
            },
        );

        go(graph, pq, dist)
    }

    let dist = BTreeMap::from([(start.to_string(), 0)]);
    let pq = BTreeSet::from([(0i32, start.to_string())]);
    go(graph, pq, dist)
}

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

    // Graph from the OCaml source:
    // a→b(1), a→c(4), b→c(2), b→d(6), c→d(3)
    // Shortest paths from a: a=0, b=1, c=3 (a→b→c), d=6 (a→b→c→d)
    fn make_graph() -> HashMap<String, Vec<(String, i32)>> {
        [
            ("a", vec![("b", 1), ("c", 4)]),
            ("b", vec![("c", 2), ("d", 6)]),
            ("c", vec![("d", 3)]),
            ("d", vec![]),
        ]
        .into_iter()
        .map(|(k, vs)| {
            (
                k.to_string(),
                vs.into_iter().map(|(v, w)| (v.to_string(), w)).collect(),
            )
        })
        .collect()
    }

    fn make_btree_graph() -> BTreeMap<String, Vec<(String, i32)>> {
        [
            ("a", vec![("b", 1), ("c", 4)]),
            ("b", vec![("c", 2), ("d", 6)]),
            ("c", vec![("d", 3)]),
            ("d", vec![]),
        ]
        .into_iter()
        .map(|(k, vs)| {
            (
                k.to_string(),
                vs.into_iter().map(|(v, w)| (v.to_string(), w)).collect(),
            )
        })
        .collect()
    }

    #[test]
    fn test_shortest_paths_from_a() {
        let dist = dijkstra(&make_graph(), "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1); // a→b direct
        assert_eq!(dist["c"], 3); // a→b→c = 1+2, not a→c direct = 4
        assert_eq!(dist["d"], 6); // a→b→c→d = 1+2+3
    }

    #[test]
    fn test_single_node_graph() {
        let graph: HashMap<String, Vec<(String, i32)>> = HashMap::from([("x".to_string(), vec![])]);
        let dist = dijkstra(&graph, "x");
        assert_eq!(dist["x"], 0);
        assert_eq!(dist.len(), 1);
    }

    #[test]
    fn test_unreachable_node_absent_from_dist() {
        // "z" exists as a node but has no incoming edges from "a"
        let mut graph = make_graph();
        graph.insert("z".to_string(), vec![]);
        let dist = dijkstra(&graph, "a");
        assert!(!dist.contains_key("z"));
    }

    #[test]
    fn test_functional_matches_idiomatic() {
        let g_hash = make_graph();
        let g_btree = make_btree_graph();
        let dist_hash = dijkstra(&g_hash, "a");
        let dist_btree = dijkstra_functional(&g_btree, "a");
        for key in ["a", "b", "c", "d"] {
            assert_eq!(dist_hash[key], dist_btree[key], "mismatch for node {key}");
        }
    }

    #[test]
    fn test_direct_edge_not_used_when_longer() {
        // a→c direct = 4, but a→b→c = 3; algorithm must choose the shorter path
        let dist = dijkstra(&make_graph(), "a");
        assert_eq!(dist["c"], 3);
    }

    #[test]
    fn test_start_from_intermediate_node() {
        // From b: b→c=2, b→d=6; then c→d gives 2+3=5 < 6
        let dist = dijkstra(&make_graph(), "b");
        assert_eq!(dist["b"], 0);
        assert_eq!(dist["c"], 2);
        assert_eq!(dist["d"], 5); // via b→c→d, not b→d directly
        assert!(!dist.contains_key("a")); // a is not reachable from b
    }

    #[test]
    fn test_linear_chain() {
        // a→b(3)→c(4)→d(5): distances should be cumulative
        let graph: HashMap<String, Vec<(String, i32)>> = [
            ("a", vec![("b", 3)]),
            ("b", vec![("c", 4)]),
            ("c", vec![("d", 5)]),
            ("d", vec![]),
        ]
        .into_iter()
        .map(|(k, vs)| {
            (
                k.to_string(),
                vs.into_iter().map(|(v, w)| (v.to_string(), w)).collect(),
            )
        })
        .collect();
        let dist = dijkstra(&graph, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 3);
        assert_eq!(dist["c"], 7);
        assert_eq!(dist["d"], 12);
    }
}

(* 1110: Dijkstra's Shortest Path — Priority Queue
   OCaml uses Set.Make as an ordered-BST priority queue and Map.Make(String)
   as the distance map. The algorithm is a tail-recursive accumulator. *)

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)

(* Idiomatic OCaml — tail-recursive via accumulator pattern.
   `go pq dist` processes the minimum-distance node from pq,
   relaxes its outgoing edges, then recurses. *)
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
  assert (SMap.find "a" dist = 0);
  assert (SMap.find "b" dist = 1);
  assert (SMap.find "c" dist = 3);  (* a→b→c = 1+2, beats a→c = 4 *)
  assert (SMap.find "d" dist = 6);  (* a→b→c→d = 1+2+3 *)
  SMap.iter (Printf.printf "%s: %d\n") dist;
  print_endline "ok"

✓ Tests Rust test suite

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

    // Graph from the OCaml source:
    // a→b(1), a→c(4), b→c(2), b→d(6), c→d(3)
    // Shortest paths from a: a=0, b=1, c=3 (a→b→c), d=6 (a→b→c→d)
    fn make_graph() -> HashMap<String, Vec<(String, i32)>> {
        [
            ("a", vec![("b", 1), ("c", 4)]),
            ("b", vec![("c", 2), ("d", 6)]),
            ("c", vec![("d", 3)]),
            ("d", vec![]),
        ]
        .into_iter()
        .map(|(k, vs)| {
            (
                k.to_string(),
                vs.into_iter().map(|(v, w)| (v.to_string(), w)).collect(),
            )
        })
        .collect()
    }

    fn make_btree_graph() -> BTreeMap<String, Vec<(String, i32)>> {
        [
            ("a", vec![("b", 1), ("c", 4)]),
            ("b", vec![("c", 2), ("d", 6)]),
            ("c", vec![("d", 3)]),
            ("d", vec![]),
        ]
        .into_iter()
        .map(|(k, vs)| {
            (
                k.to_string(),
                vs.into_iter().map(|(v, w)| (v.to_string(), w)).collect(),
            )
        })
        .collect()
    }

    #[test]
    fn test_shortest_paths_from_a() {
        let dist = dijkstra(&make_graph(), "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1); // a→b direct
        assert_eq!(dist["c"], 3); // a→b→c = 1+2, not a→c direct = 4
        assert_eq!(dist["d"], 6); // a→b→c→d = 1+2+3
    }

    #[test]
    fn test_single_node_graph() {
        let graph: HashMap<String, Vec<(String, i32)>> = HashMap::from([("x".to_string(), vec![])]);
        let dist = dijkstra(&graph, "x");
        assert_eq!(dist["x"], 0);
        assert_eq!(dist.len(), 1);
    }

    #[test]
    fn test_unreachable_node_absent_from_dist() {
        // "z" exists as a node but has no incoming edges from "a"
        let mut graph = make_graph();
        graph.insert("z".to_string(), vec![]);
        let dist = dijkstra(&graph, "a");
        assert!(!dist.contains_key("z"));
    }

    #[test]
    fn test_functional_matches_idiomatic() {
        let g_hash = make_graph();
        let g_btree = make_btree_graph();
        let dist_hash = dijkstra(&g_hash, "a");
        let dist_btree = dijkstra_functional(&g_btree, "a");
        for key in ["a", "b", "c", "d"] {
            assert_eq!(dist_hash[key], dist_btree[key], "mismatch for node {key}");
        }
    }

    #[test]
    fn test_direct_edge_not_used_when_longer() {
        // a→c direct = 4, but a→b→c = 3; algorithm must choose the shorter path
        let dist = dijkstra(&make_graph(), "a");
        assert_eq!(dist["c"], 3);
    }

    #[test]
    fn test_start_from_intermediate_node() {
        // From b: b→c=2, b→d=6; then c→d gives 2+3=5 < 6
        let dist = dijkstra(&make_graph(), "b");
        assert_eq!(dist["b"], 0);
        assert_eq!(dist["c"], 2);
        assert_eq!(dist["d"], 5); // via b→c→d, not b→d directly
        assert!(!dist.contains_key("a")); // a is not reachable from b
    }

    #[test]
    fn test_linear_chain() {
        // a→b(3)→c(4)→d(5): distances should be cumulative
        let graph: HashMap<String, Vec<(String, i32)>> = [
            ("a", vec![("b", 3)]),
            ("b", vec![("c", 4)]),
            ("c", vec![("d", 5)]),
            ("d", vec![]),
        ]
        .into_iter()
        .map(|(k, vs)| {
            (
                k.to_string(),
                vs.into_iter().map(|(v, w)| (v.to_string(), w)).collect(),
            )
        })
        .collect();
        let dist = dijkstra(&graph, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 3);
        assert_eq!(dist["c"], 7);
        assert_eq!(dist["d"], 12);
    }
}

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)

pub fn dijkstra(
    graph: &HashMap<String, Vec<(String, i32)>>,
    start: &str,
) -> HashMap<String, i32> {
    let mut dist: HashMap<String, i32> = HashMap::from([(start.to_string(), 0)]);
    let mut heap: BinaryHeap<Reverse<(i32, String)>> =
        BinaryHeap::from([Reverse((0, start.to_string()))]);

    while let Some(Reverse((d, u))) = heap.pop() {
        // stale-entry filter: replaces OCaml Set's no-duplicate guarantee
        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;
            if alt < dist.get(v).copied().unwrap_or(i32::MAX) {
                dist.insert(v.clone(), alt);
                heap.push(Reverse((alt, v.clone())));
            }
        }
    }
    dist
}

Rust (functional / set-based)

pub fn dijkstra_functional(
    graph: &BTreeMap<String, Vec<(String, i32)>>,
    start: &str,
) -> BTreeMap<String, i32> {
    fn go(
        graph: &BTreeMap<String, Vec<(String, i32)>>,
        mut pq: BTreeSet<(i32, String)>,
        mut dist: BTreeMap<String, i32>,
    ) -> BTreeMap<String, i32> {
        let Some((d, u)) = pq.pop_first() else { return dist };

        let (dist, pq) = graph
            .get(&u)
            .map(Vec::as_slice)
            .unwrap_or(&[])
            .iter()
            .fold((dist, pq), |(mut dist, mut pq), (v, w)| {
                let alt = d + w;
                if alt < dist.get(v).copied().unwrap_or(i32::MAX) {
                    dist.insert(v.clone(), alt);
                    pq.insert((alt, v.clone()));
                }
                (dist, pq)
            });

        go(graph, pq, dist)
    }

    let dist = BTreeMap::from([(start.to_string(), 0)]);
    let pq = BTreeSet::from([(0i32, start.to_string())]);
    go(graph, pq, dist)
}

Type Signatures

Concept	OCaml	Rust (idiomatic)
Graph type	`(string * int) list SMap.t`	`&HashMap<String, Vec<(String, i32)>>`
Distance map	`int SMap.t` (persistent)	`HashMap<String, i32>` (mutable)
Priority queue	`PQ.t` (ordered BST, no duplicates)	`BinaryHeap<Reverse<(i32, String)>>`
Min extraction	`PQ.min_elt pq` + `PQ.remove`	`heap.pop()`
Not-found default	`try find v dist with Not_found -> max_int`	`.unwrap_or(i32::MAX)`
Function signature	`val dijkstra : ... SMap.t -> string -> int SMap.t`	`fn dijkstra(&HashMap<..>, &str) -> HashMap<String, i32>`

Key Insights

Priority queue: Set vs Heap. OCaml's Set.Make is a balanced BST — inserting (alt, v) when a shorter path is found automatically replaces any existing entry for the same (d, v) pair if one exists (because the comparison function treats them as distinct keys). Rust's BinaryHeap allows unlimited duplicates; when a node's distance improves, the old entry remains in the heap. The stale-entry check (d > dist[u] → continue) makes this safe with zero extra bookkeeping.

Atomic pop. OCaml requires two calls — PQ.min_elt to peek and PQ.remove to delete. The functional Rust version uses BTreeSet::pop_first() (stable since Rust 1.66) which atomically removes and returns the minimum, eliminating the need to clone the key just for the removal call.

Persistent vs mutable maps. OCaml's Map.add v alt dist returns a new map, leaving the original unchanged — this is what makes the fold accumulator pattern work without explicit mutation. Rust's HashMap::insert mutates in place. The functional Rust variant uses mut dist inside closures, which is idiomatic Rust — there is no mut at the call site because the map is passed by ownership through the fold accumulator.

Tail-call optimisation. OCaml guarantees that let rec go pq dist = ... go pq dist compiles to a loop (TCO). Rust has no such guarantee; the recursive dijkstra_functional will stack-overflow on deep graphs. The idiomatic while let loop in dijkstra is always safe. For production use, always prefer the iterative form in Rust.

Exception vs Option for defaults. OCaml uses try SMap.find v dist with Not_found -> max_int — an exception is thrown and caught to supply the default distance. Rust uses HashMap::get(v).copied().unwrap_or(i32::MAX) — the same default is expressed as a pure Option combinator chain, with no implicit control-flow transfer.

When to Use Each Style

**Use idiomatic Rust (BinaryHeap + HashMap) when:** writing production or performance-sensitive code. Binary heap has O(1) amortized push and O(log n) pop; HashMap has O(1) amortized lookup. No stack-overflow risk.

**Use functional Rust (BTreeSet + BTreeMap) when:** porting OCaml code directly for educational purposes, or when you need the distance map to be naturally sorted in the output (e.g. for deterministic iteration order in tests or reports).

Exercises

Add a path_to function that reconstructs the sequence of node IDs forming the shortest path from source to target, returning None if the target is unreachable.

Extend the graph to support directed vs. undirected edges and verify that shortest paths differ appropriately for each graph type.

Implement A* search on the same graph representation by adding a heuristic function parameter, and compare the number of nodes expanded vs. plain Dijkstra on a grid graph.

Open Source Repos

functional-rust

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

Rust