Step 5 of 7

Dijkstra's shortest paths with BinaryHeap

When edges have weights (kilometers, minutes, milliseconds of latency, euros), the path with the fewest edges isn't necessarily the cheapest. Dijkstra's algorithm finds the cheapest path from one start node to every other node, as long as no weight is negative.

The idea: repeatedly take the not-yet-settled node with the smallest known distance. Its distance is final, because any other way to reach it would go through a node that is already at least as far away. Then try to improve its neighbors' distances through it (relaxing the edges).

"Take the node with the smallest distance" is exactly what a min-heap is for: a BinaryHeap<Reverse<(u64, usize)>> of (distance, node) pairs. Rust's heap can't lower an item's priority in place, so when a distance improves you simply push a new pair; when an outdated pair pops later (its distance is bigger than the best known one), you skip it. This is called lazy deletion.

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

fn dijkstra(adj: &[Vec<(usize, u64)>], start: usize) -> Vec<u64> {
    let mut dist = vec![u64::MAX; adj.len()]; // u64::MAX = not reached
    let mut heap = BinaryHeap::new();
    dist[start] = 0;
    heap.push(Reverse((0, start)));
    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
            continue; // stale entry: a shorter way to u was found later
        }
        for &(v, weight) in &adj[u] {
            let through_u = d + weight;
            if through_u < dist[v] {
                dist[v] = through_u;
                heap.push(Reverse((through_u, v)));
            }
        }
    }
    dist
}

fn main() {
    // warehouse 0 and four shops; (to, minutes) one-way roads
    let adj = vec![
        vec![(1, 4), (2, 1)],
        vec![(3, 1)],
        vec![(1, 2), (3, 5)],
        vec![],
        vec![(0, 3)],
    ];
    for (shop, d) in dijkstra(&adj, 0).iter().enumerate() {
        if *d == u64::MAX {
            println!("shop {shop}: unreachable");
        } else {
            println!("shop {shop}: {d} min");
        }
    }
}

shop 0: 0 min
shop 1: 3 min
shop 2: 1 min
shop 3: 4 min
shop 4: unreachable

Shop 1 is 4 minutes away directly, but 3 minutes via shop 2: Dijkstra settles shop 2 first (distance 1), improves shop 1 to 3, and later skips the stale (4, 1) entry.

Each edge can push one heap entry, and each push or pop costs O(log V), so the whole thing is O((V + E) log V). Navigation apps, network routing protocols (OSPF) and game pathfinding (A*, which adds a distance estimate) all build on it.

Common mistakes

• Negative weights. A settled distance could still be beaten later; Dijkstra gives wrong answers. (Bellman-Ford handles negative weights, more slowly.)
• A max-heap. Without Reverse, the heap hands you the farthest node first.
• No stale check. Without if d > dist[u] { continue; }, outdated entries re-relax edges with wrong distances (wasted work, and wrong answers in variants).
• Overflow. u64::MAX + weight panics in a debug build. Only add weights to distances you've actually reached (popped nodes always have one).
• Putting the node first in the tuple. The heap orders tuples by their first field, so it must be the distance.

Your task

Write fn shortest_times(adj: &[Vec<(usize, u64)>], start: usize) -> Vec<Option<u64>> that returns the cheapest total weight from start to every node (None for unreachable nodes). The graph is directed: adj[u] lists (v, weight) pairs. The tests include 100,000 nodes and 300,000 edges.

Challenge 2

A message is broadcast from server source across a network of n servers (0..n). Each link (from, to, millis) carries it one way in that many milliseconds. Write fn time_to_reach_all(n: usize, links: &[(usize, usize, u64)], source: usize) -> Option<u64>: how long until every server has the message (the largest shortest-path distance), or None if some server never gets it.

Build adjacency lists from the links, run Dijkstra from source, then take the maximum distance.

Challenge 3

Build the route planner for a delivery company. Standard input starts with a line FROM TO, followed by roads, one per line: CITY CITY MINUTES (roads go both ways). Print the cheapest route as the cities joined by -> with the total in parentheses, like Aston -> Cobb -> Bree (8), or no route. If FROM and TO are the same city, print just that city with (0). In every test the cheapest route is unique.

Give each city an index with a HashMap<String, usize> and keep the names in a Vec<String>. Run Dijkstra with a parent array, as you did for BFS routes, and walk it back from TO.

Previous: Topological sort: ordering tasks with dependencies Next: Binary trees with Option<Box<Node>>