Dijkstra with BinaryHeap

Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a graph with non-negative edge weights ($w(u, v) \ge 0$) in $O((V + E) \log V)$ time. In Rust, Dijkstra's algorithm is implemented using std::collections::BinaryHeap wrapped with std::cmp::Reverse<(Cost, Vertex)> so the minimum-distance frontier vertex is always popped first.

Lazy Deletion Min-Heap Dijkstra Pattern:
  1. Pop `Reverse((d, u))` from `BinaryHeap`
  2. Lazy Stale Check: `if d > dist[u] { continue; }`  <-- Skips outdated heap entries in O(1)!
  3. For each outgoing edge `(u -> v, weight)`:
     If `d + weight < dist[v]`:
       `dist[v] = d + weight;`
       `prev[v] = Some(u);`
       `heap.push(Reverse((dist[v], v)));`

Two Essential Details in Rust's BinaryHeap Dijkstra

1. Tuple Element Ordering ((distance, vertex)): Rust tuples compare lexicographically from left to right. Always place the distance/cost first and the vertex index second (Reverse((dist, u))), so the heap orders primarily by shortest distance!
2. Lazy Deletion (if d > dist[u] { continue; }): Because std::collections::BinaryHeap does not expose a decrease_key operation, pushing a new shorter entry Reverse((new_d, v)) whenever a shorter path to v is found is actually faster in practice on sparse graphs than maintaining an auxiliary heap-index map—provided you immediately discard stale entries with if d > dist[u] { continue; } when popping!

Complete Dijkstra Implementation with Shortest-Path Reconstruction

By recording parent: Vec<Option<usize>> alongside dist: Vec<u64>, you can reconstruct the exact sequence of vertices along the shortest path from start to target by walking backward from target and reversing the result:

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

pub struct ShortestPathResult {
    pub distances: Vec<u64>,
    pub parents: Vec<Option<usize>>,
}

impl ShortestPathResult {
    /// Reconstructs the exact vertex path `start -> ... -> target` if reachable.
    pub fn path_to(&self, target: usize) -> Option<Vec<usize>> {
        if self.distances[target] == u64::MAX {
            return None;
        }
        let mut path = Vec::new();
        let mut cur = Some(target);
        while let Some(u) = cur {
            path.push(u);
            cur = self.parents[u];
        }
        path.reverse();
        Some(path)
    }
}

pub fn dijkstra_with_paths(adj: &[Vec<(usize, u64)>], start: usize) -> ShortestPathResult {
    let n = adj.len();
    let mut distances = vec![u64::MAX; n];
    let mut parents = vec![None; n];
    let mut pq: BinaryHeap<Reverse<(u64, usize)>> = BinaryHeap::new();

    distances[start] = 0;
    pq.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = pq.pop() {
        // Lazy deletion check: ignore stale entries!
        if d > distances[u] {
            continue;
        }

        for &(v, weight) in &adj[u] {
            let next_d = d.saturating_add(weight);
            if next_d < distances[v] {
                distances[v] = next_d;
                parents[v] = Some(u);
                pq.push(Reverse((next_d, v)));
            }
        }
    }

    ShortestPathResult { distances, parents }
}

fn main() {
    // Graph:
    // 0 --(10)--> 1 --(1)--> 3
    // 0 --(3)---> 2 --(4)--> 1
    //             2 --(8)--> 3
    // Shortest path 0 -> 3 is: 0 -> 2 (3) -> 1 (7) -> 3 (8)
    let adj = vec![
        vec![(1, 10), (2, 3)],
        vec![(3, 1)],
        vec![(1, 4), (3, 8)],
        vec![],
    ];

    let res = dijkstra_with_paths(&adj, 0);
    assert_eq!(res.distances, vec![0, 7, 3, 8]);
    assert_eq!(res.path_to(3), Some(vec![0, 2, 1, 3]));

    println!(
        "Shortest distance 0 -> 3: {}, path: {:?}",
        res.distances[3],
        res.path_to(3).unwrap()
    );
}

Shortest distance 0 -> 3: 8, path: [0, 2, 1, 3]