1099 Advanced

Dijkstra's Shortest Path with Priority Queue

GraphsPriority Queues

Tutorial Video

Text description (accessibility)

This video demonstrates the "Dijkstra's Shortest Path with Priority Queue" functional Rust example. Difficulty level: Advanced. Key concepts covered: Graphs, Priority Queues. Implement Dijkstra's single-source shortest path algorithm using a priority queue. Key difference from OCaml: 1. **Priority queue:** OCaml uses `Set.Make` (balanced BST, O(log n) insert/remove/min); Rust idiomatically uses `BinaryHeap` (binary heap, O(log n) push/pop) with `Reverse` for min

Tutorial

The Problem

Implement Dijkstra's single-source shortest path algorithm using a priority queue. Given a weighted directed graph and a start node, compute the minimum distance from the start to every reachable node.

🎯 Learning Outcomes

• How Rust's BinaryHeap with Reverse serves as a min-priority queue (vs OCaml's Set.Make)

• Threading mutable state through a loop vs OCaml's recursive accumulation of immutable maps

• Using HashMap for O(1) distance lookups compared to OCaml's Map (balanced tree, O(log n))

• How BTreeSet in Rust can mirror OCaml's ordered-set-as-priority-queue pattern directly

🦀 The Rust Way

The idiomatic Rust solution uses BinaryHeap<Reverse<(u64, &str)>> as a min-heap priority queue with HashMap for O(1) distance lookups. A "stale entry" check skips nodes whose distance was already improved. The functional variant mirrors OCaml closely using BTreeSet (ordered, supports iter().next() for min extraction) and fold for neighbor relaxation. A third variant uses an explicit HashSet for visited-node tracking.

Code Example

pub fn dijkstra_idiomatic<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64> {
    let mut dist: HashMap<&'a str, u64> = HashMap::new();
    let mut heap: BinaryHeap<Reverse<(u64, &'a str)>> = BinaryHeap::new();

    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > *dist.get(u).unwrap_or(&u64::MAX) {
            continue;
        }
        if let Some(neighbors) = graph.get(u) {
            for &(v, w) in neighbors {
                let alt = d + w;
                let current = *dist.get(v).unwrap_or(&u64::MAX);
                if alt < current {
                    dist.insert(v, alt);
                    heap.push(Reverse((alt, v)));
                }
            }
        }
    }
    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 uses Set.Make (balanced BST, O(log n) insert/remove/min); Rust idiomatically uses BinaryHeap (binary heap, O(log n) push/pop) with Reverse for min-ordering

Distance map: OCaml's Map is a persistent balanced tree; Rust's HashMap provides O(1) amortized lookups with in-place mutation

State threading: OCaml recurses with go pq dist passing immutable structures; Rust mutates dist and heap in a while let loop

Missing keys: OCaml catches Not_found exceptions; Rust uses .get().unwrap_or(&u64::MAX) — no exceptions needed

OCaml Approach

OCaml uses Set.Make with a custom comparator on (int * string) tuples to create an ordered set that doubles as a priority queue — min_elt always returns the closest unvisited node. Distances are tracked in an immutable Map.Make(String), and the algorithm recurses with go pq dist, threading both structures as arguments. List.fold_left relaxes neighbors functionally, producing updated (dist, pq) pairs without mutation.

Full Source

#![allow(clippy::all)]
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

/// Adjacency list representation: node -> [(neighbor, weight)]
pub type Graph<'a> = HashMap<&'a str, Vec<(&'a str, u64)>>;

// ---------------------------------------------------------------------------
// Solution 1: Idiomatic Rust — BinaryHeap as a min-priority queue
// Uses Reverse to turn the max-heap into a min-heap, iterators for neighbor
// relaxation, and HashMap for O(1) distance lookups.
// ---------------------------------------------------------------------------
pub fn dijkstra_idiomatic<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64> {
    let mut dist: HashMap<&'a str, u64> = HashMap::new();
    let mut heap: BinaryHeap<Reverse<(u64, &'a str)>> = BinaryHeap::new();

    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = heap.pop() {
        // Skip stale entries — we already found a shorter path
        if d > *dist.get(u).unwrap_or(&u64::MAX) {
            continue;
        }

        if let Some(neighbors) = graph.get(u) {
            for &(v, w) in neighbors {
                let alt = d + w;
                let current = *dist.get(v).unwrap_or(&u64::MAX);
                if alt < current {
                    dist.insert(v, alt);
                    heap.push(Reverse((alt, v)));
                }
            }
        }
    }

    dist
}

// ---------------------------------------------------------------------------
// Solution 2: Functional/recursive — mirrors the OCaml structure
// Uses a BTreeSet as an ordered set (like OCaml's Set.Make) to always extract
// the minimum element. Accumulates distances in a HashMap, threading state
// through recursive calls just like the OCaml version's `go pq dist`.
// ---------------------------------------------------------------------------
pub fn dijkstra_functional<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64> {
    use std::collections::BTreeSet;

    // BTreeSet<(u64, &str)> — ordered by distance then node name, like OCaml's PQ
    type Pq<'a> = BTreeSet<(u64, &'a str)>;

    fn go<'a>(graph: &Graph<'a>, pq: Pq<'a>, dist: HashMap<&'a str, u64>) -> HashMap<&'a str, u64> {
        // Base case: empty priority queue — return accumulated distances
        let &(d, u) = match pq.iter().next() {
            None => return dist,
            Some(min) => min,
        };

        let mut pq = pq;
        pq.remove(&(d, u));

        // Skip stale entries
        if d > *dist.get(u).unwrap_or(&u64::MAX) {
            return go(graph, pq, dist);
        }

        // Fold over neighbors — functional accumulation of (dist, pq)
        let empty: Vec<(&str, u64)> = Vec::new();
        let neighbors = graph.get(u).unwrap_or(&empty);
        let (dist, pq) = neighbors
            .iter()
            .fold((dist, pq), |(mut dist, mut pq), &(v, w)| {
                let alt = d + w;
                let current = *dist.get(v).unwrap_or(&u64::MAX);
                if alt < current {
                    dist.insert(v, alt);
                    pq.insert((alt, v));
                }
                (dist, pq)
            });

        go(graph, pq, dist)
    }

    let mut dist = HashMap::new();
    dist.insert(start, 0);
    let mut pq = BTreeSet::new();
    pq.insert((0u64, start));

    go(graph, pq, dist)
}

// ---------------------------------------------------------------------------
// Solution 3: Iterator-based relaxation with explicit visited set
// Separates the "visited" concept from distance tracking for clarity.
// ---------------------------------------------------------------------------
pub fn dijkstra_visited<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64> {
    use std::collections::HashSet;

    let mut dist: HashMap<&'a str, u64> = HashMap::new();
    let mut visited: HashSet<&'a str> = HashSet::new();
    let mut heap: BinaryHeap<Reverse<(u64, &'a str)>> = BinaryHeap::new();

    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if !visited.insert(u) {
            continue; // Already processed this node
        }

        let neighbors = graph.get(u).into_iter().flatten();
        for &(v, w) in neighbors {
            let alt = d + w;
            let current = *dist.get(v).unwrap_or(&u64::MAX);
            if alt < current {
                dist.insert(v, alt);
                heap.push(Reverse((alt, v)));
            }
        }
    }

    dist
}

/// Helper to build a graph from a slice of (node, neighbors) pairs
pub fn build_graph<'a>(edges: &[(&'a str, Vec<(&'a str, u64)>)]) -> Graph<'a> {
    edges.iter().cloned().collect()
}

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

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

    // -- Idiomatic --

    #[test]
    fn idiomatic_basic_shortest_paths() {
        let g = sample_graph();
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3); // a->b->c = 1+2 = 3, shorter than a->c = 4
        assert_eq!(dist["d"], 6); // a->b->c->d = 1+2+3 = 6, shorter than a->b->d = 7
    }

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

    #[test]
    fn idiomatic_disconnected_node() {
        let g = build_graph(&[("a", vec![("b", 5)]), ("b", vec![]), ("c", vec![])]);
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 5);
        assert!(!dist.contains_key("c")); // c unreachable from a
    }

    #[test]
    fn idiomatic_multiple_paths_picks_shortest() {
        // a->b: 10, a->c: 1, c->b: 2 — shortest to b is a->c->b = 3
        let g = build_graph(&[
            ("a", vec![("b", 10), ("c", 1)]),
            ("c", vec![("b", 2)]),
            ("b", vec![]),
        ]);
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist["b"], 3);
    }

    // -- Functional --

    #[test]
    fn functional_basic_shortest_paths() {
        let g = sample_graph();
        let dist = dijkstra_functional(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3);
        assert_eq!(dist["d"], 6);
    }

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

    #[test]
    fn functional_disconnected_node() {
        let g = build_graph(&[("a", vec![("b", 5)]), ("b", vec![]), ("c", vec![])]);
        let dist = dijkstra_functional(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 5);
        assert!(!dist.contains_key("c"));
    }

    #[test]
    fn functional_matches_idiomatic() {
        let g = sample_graph();
        let d1 = dijkstra_idiomatic(&g, "a");
        let d2 = dijkstra_functional(&g, "a");
        assert_eq!(d1, d2);
    }

    // -- Visited --

    #[test]
    fn visited_basic_shortest_paths() {
        let g = sample_graph();
        let dist = dijkstra_visited(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3);
        assert_eq!(dist["d"], 6);
    }

    #[test]
    fn visited_matches_idiomatic() {
        let g = sample_graph();
        let d1 = dijkstra_idiomatic(&g, "a");
        let d2 = dijkstra_visited(&g, "a");
        assert_eq!(d1, d2);
    }

    #[test]
    fn all_implementations_agree_on_linear_chain() {
        // a->b->c->d->e, each edge weight 1
        let g = build_graph(&[
            ("a", vec![("b", 1)]),
            ("b", vec![("c", 1)]),
            ("c", vec![("d", 1)]),
            ("d", vec![("e", 1)]),
            ("e", vec![]),
        ]);
        let d1 = dijkstra_idiomatic(&g, "a");
        let d2 = dijkstra_functional(&g, "a");
        let d3 = dijkstra_visited(&g, "a");
        assert_eq!(d1, d2);
        assert_eq!(d2, d3);
        assert_eq!(d1["e"], 4);
    }

    #[test]
    fn empty_graph_start_only() {
        let g: Graph = HashMap::new();
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist.len(), 1);
        assert_eq!(dist["a"], 0);
    }
}

(* Dijkstra's shortest path using a priority queue (ordered set) *)

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 — immutable maps and sets, recursive loop *)
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);
  assert (SMap.find "d" dist = 6);
  (* Single node *)
  let g2 = SMap.singleton "x" [] in
  let dist2 = dijkstra g2 "x" in
  assert (SMap.find "x" dist2 = 0);
  assert (SMap.cardinal dist2 = 1);
  print_endline "ok"

✓ Tests Rust test suite

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

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

    // -- Idiomatic --

    #[test]
    fn idiomatic_basic_shortest_paths() {
        let g = sample_graph();
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3); // a->b->c = 1+2 = 3, shorter than a->c = 4
        assert_eq!(dist["d"], 6); // a->b->c->d = 1+2+3 = 6, shorter than a->b->d = 7
    }

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

    #[test]
    fn idiomatic_disconnected_node() {
        let g = build_graph(&[("a", vec![("b", 5)]), ("b", vec![]), ("c", vec![])]);
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 5);
        assert!(!dist.contains_key("c")); // c unreachable from a
    }

    #[test]
    fn idiomatic_multiple_paths_picks_shortest() {
        // a->b: 10, a->c: 1, c->b: 2 — shortest to b is a->c->b = 3
        let g = build_graph(&[
            ("a", vec![("b", 10), ("c", 1)]),
            ("c", vec![("b", 2)]),
            ("b", vec![]),
        ]);
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist["b"], 3);
    }

    // -- Functional --

    #[test]
    fn functional_basic_shortest_paths() {
        let g = sample_graph();
        let dist = dijkstra_functional(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3);
        assert_eq!(dist["d"], 6);
    }

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

    #[test]
    fn functional_disconnected_node() {
        let g = build_graph(&[("a", vec![("b", 5)]), ("b", vec![]), ("c", vec![])]);
        let dist = dijkstra_functional(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 5);
        assert!(!dist.contains_key("c"));
    }

    #[test]
    fn functional_matches_idiomatic() {
        let g = sample_graph();
        let d1 = dijkstra_idiomatic(&g, "a");
        let d2 = dijkstra_functional(&g, "a");
        assert_eq!(d1, d2);
    }

    // -- Visited --

    #[test]
    fn visited_basic_shortest_paths() {
        let g = sample_graph();
        let dist = dijkstra_visited(&g, "a");
        assert_eq!(dist["a"], 0);
        assert_eq!(dist["b"], 1);
        assert_eq!(dist["c"], 3);
        assert_eq!(dist["d"], 6);
    }

    #[test]
    fn visited_matches_idiomatic() {
        let g = sample_graph();
        let d1 = dijkstra_idiomatic(&g, "a");
        let d2 = dijkstra_visited(&g, "a");
        assert_eq!(d1, d2);
    }

    #[test]
    fn all_implementations_agree_on_linear_chain() {
        // a->b->c->d->e, each edge weight 1
        let g = build_graph(&[
            ("a", vec![("b", 1)]),
            ("b", vec![("c", 1)]),
            ("c", vec![("d", 1)]),
            ("d", vec![("e", 1)]),
            ("e", vec![]),
        ]);
        let d1 = dijkstra_idiomatic(&g, "a");
        let d2 = dijkstra_functional(&g, "a");
        let d3 = dijkstra_visited(&g, "a");
        assert_eq!(d1, d2);
        assert_eq!(d2, d3);
        assert_eq!(d1["e"], 4);
    }

    #[test]
    fn empty_graph_start_only() {
        let g: Graph = HashMap::new();
        let dist = dijkstra_idiomatic(&g, "a");
        assert_eq!(dist.len(), 1);
        assert_eq!(dist["a"], 0);
    }
}

Deep Comparison

OCaml vs Rust: Dijkstra's Shortest Path with 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_idiomatic<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64> {
    let mut dist: HashMap<&'a str, u64> = HashMap::new();
    let mut heap: BinaryHeap<Reverse<(u64, &'a str)>> = BinaryHeap::new();

    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if d > *dist.get(u).unwrap_or(&u64::MAX) {
            continue;
        }
        if let Some(neighbors) = graph.get(u) {
            for &(v, w) in neighbors {
                let alt = d + w;
                let current = *dist.get(v).unwrap_or(&u64::MAX);
                if alt < current {
                    dist.insert(v, alt);
                    heap.push(Reverse((alt, v)));
                }
            }
        }
    }
    dist
}

Rust (functional/recursive)

pub fn dijkstra_functional<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64> {
    type Pq<'a> = BTreeSet<(u64, &'a str)>;

    fn go<'a>(graph: &Graph<'a>, pq: Pq<'a>, dist: HashMap<&'a str, u64>) -> HashMap<&'a str, u64> {
        let &(d, u) = match pq.iter().next() {
            None => return dist,
            Some(min) => min,
        };
        let mut pq = pq;
        pq.remove(&(d, u));

        if d > *dist.get(u).unwrap_or(&u64::MAX) {
            return go(graph, pq, dist);
        }

        let empty: Vec<(&str, u64)> = Vec::new();
        let neighbors = graph.get(u).unwrap_or(&empty);
        let (dist, pq) = neighbors.iter()
            .fold((dist, pq), |(mut dist, mut pq), &(v, w)| {
                let alt = d + w;
                let current = *dist.get(v).unwrap_or(&u64::MAX);
                if alt < current {
                    dist.insert(v, alt);
                    pq.insert((alt, v));
                }
                (dist, pq)
            });
        go(graph, pq, dist)
    }

    let mut dist = HashMap::new();
    dist.insert(start, 0);
    let mut pq = BTreeSet::new();
    pq.insert((0u64, start));
    go(graph, pq, dist)
}

Type Signatures

Concept	OCaml	Rust
Graph type	`(string * int) list SMap.t`	`HashMap<&str, Vec<(&str, u64)>>`
Priority queue	`PQ.t` (Set of `int * string`)	`BinaryHeap<Reverse<(u64, &str)>>`
Distance map	`int SMap.t`	`HashMap<&str, u64>`
Function signature	`val dijkstra : (string * int) list SMap.t -> string -> int SMap.t`	`fn dijkstra<'a>(graph: &Graph<'a>, start: &'a str) -> HashMap<&'a str, u64>`
Missing key	`Not_found` exception	`.get().unwrap_or(&u64::MAX)`

Key Insights

Priority queue duality: OCaml's Set.Make serves as both a sorted collection and a priority queue (via min_elt). Rust separates these — BinaryHeap for priority queues, BTreeSet for ordered sets. The functional Rust version uses BTreeSet to mirror the OCaml approach directly.

Ownership threading: OCaml's go pq dist passes immutable values that are structurally shared. Rust's functional version moves ownership of HashMap and BTreeSet through each recursive call — no cloning needed because we transfer, not share.

Error handling vs defaults: OCaml uses try ... with Not_found exception handling for missing map keys. Rust uses .get().unwrap_or(&u64::MAX) — a combinator approach that avoids exceptions entirely and is branch-predictor friendly.

Stale entry handling: Both versions may push duplicate entries into the priority queue. OCaml's set automatically deduplicates by (distance, node) pair. Rust's BinaryHeap does not deduplicate, so we check d > dist[u] to skip stale entries.

Lifetime annotations: Rust requires explicit 'a lifetimes to prove that node references (&'a str) in the result live as long as the input graph. OCaml's GC handles this implicitly — the string values just stay alive as long as they're referenced.

When to Use Each Style

Use idiomatic Rust when: Building production graph algorithms — BinaryHeap with Reverse is the standard Rust pattern for Dijkstra, offers excellent cache performance, and the imperative loop is clear and efficient.

Use recursive Rust when: Teaching the algorithm's structure or when you want a direct translation from a functional specification — the BTreeSet + fold + recursion pattern maps 1:1 to the OCaml and makes correctness reasoning easier.

Exercises

Extend Dijkstra's implementation to reconstruct the full shortest path (not just the distance) by recording predecessor nodes during relaxation.

Modify the algorithm to find the shortest path with at most k hops and return None if no such path exists within the hop limit.

Implement Bellman–Ford on the same graph representation and compare results with Dijkstra on a graph that contains negative-weight edges (but no negative cycles).

Open Source Repos

functional-rust

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

Rust