Shortest paths in Rust

You type your college into a map app, and it shows a route. Behind that route, the app has quietly looked at thousands of roads, and picked the cheapest way to add them up.

That is the shortest path problem. You have a graph (lesson 10), a starting place, and a goal. Find the route whose total cost is as small as possible. "Cost" can be kilometres, minutes, rupees, or anything you want to keep small.

There are two cases, and each has its own tool.

• If every road counts the same, "shortest" just means fewest roads. You already have the tool: BFS from lesson 17.
• If roads have different lengths, a route with fewer roads can be longer. You need Dijkstra's algorithm (said "DYKE-struh"), named after the Dutch computer scientist who invented it.

Reach for these when a question asks for the fewest moves, the cheapest trip, the fastest signal, or the least effort between two things.

Fewest roads. BFS spreads out in rings, so the first time it reaches a place, it got there in the fewest steps. To recover the route and not only the count, remember where you came from. Each time the search first reaches a place, write down the place before it. At the end, follow those notes backwards from the goal to the start, and flip the list round.

Roads with lengths. Look at the map. The direct road from A to B has length 4. But A to C is 2, and C to B is 1, so going round through C costs only 3. A straight-line guess is not enough. You need a plan that is sure to find the best.

Dijkstra's plan is simple. Keep the best distance known so far to every place, starting with 0 for home and "unknown" for the rest. Then repeat one move: pick the closest place not yet settled, and use it to improve its neighbours.

Try it on the map. Home A is at 0. Its roads give B a distance of 4 and C a distance of 2. The closest unsettled place is C, at 2. Settle it. Its roads give B a new distance of 2 + 1 = 3, which beats 4, and D a distance of 2 + 8 = 10. Next closest is B, at 3. Settle it. It gives D a distance of 3 + 5 = 8, which beats 10. Then D at 8 gives E a distance of 11. Done: 0, 3, 2, 8 and 11.

Why is picking the closest place safe? Because every road has a length of zero or more. Any other route to the closest place would have to go through some place that is further away already, so it cannot be shorter. Once a place is the closest, its distance is final. This is exactly why Dijkstra does not work if a road can have a negative length: a later detour could undo a "final" answer.

Which data structure finds the closest unsettled place quickly? A priority queue, the heap from lesson 8. Each entry is a pair: a distance and a place. You pop the smallest distance each time.

One small wrinkle: when a better distance to a place turns up, the old, longer entry for it is still in the heap. Rather than hunt it down, leave it there, and skip it when it comes out. You can tell it is stale because its distance is bigger than the best known.

Remember: BFS for fewest roads. For roads with lengths, always settle the closest place next, using a heap.

First, the fewest-roads route. It is BFS with a parent list.

use std::collections::VecDeque;

/// The fewest-roads route from `from` to `to`, listing every stop on the way,
/// or `None` if there is no route. Every road counts as one step.
pub fn shortest_path(adj: &[Vec<usize>], from: usize, to: usize) -> Option<Vec<usize>> {
    // `parent[v]` is the stop we came from when the ripple first reached `v`.
    let mut parent: Vec<Option<usize>> = vec![None; adj.len()];
    let mut visited = vec![false; adj.len()];
    let mut queue = VecDeque::from([from]);
    visited[from] = true;

    while let Some(v) = queue.pop_front() {
        if v == to {
            break;
        }
        for &w in &adj[v] {
            if !visited[w] {
                visited[w] = true;
                parent[w] = Some(v);
                queue.push_back(w);
            }
        }
    }
    if !visited[to] {
        return None;
    }

    // Walk back from the end to the start, then flip the list round.
    let mut route = vec![to];
    let mut here = to;
    while let Some(before) = parent[here] {
        route.push(before);
        here = before;
    }
    route.reverse();
    Some(route)
}

Go through it in order.

• parent[w] holds the place we stepped from when we first reached w. It starts as None for everyone.
• The BFS loop is the one from lesson 17. The only new line is parent[w] = Some(v). We can stop early once we pop the goal.
• If the goal was never reached, there is no route, and the answer is None.
• Otherwise, start at to and keep stepping to parent[here] until there is none left, which only happens at the start. That gives the route backwards, so reverse() flips it.

Now the weighted version. Each neighbour in the list also carries the length of its road, so the list holds pairs.

/// Two-way roads with a length. `graph[v]` lists `(neighbour, length)` pairs.
pub fn weighted_graph(n: usize, roads: &[(usize, usize, u32)]) -> Vec<Vec<(usize, u32)>> {
    let mut graph = vec![Vec::new(); n];
    for &(a, b, length) in roads {
        graph[a].push((b, length));
        graph[b].push((a, length));
    }
    graph
}

And Dijkstra itself.

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

/// The shortest total length from `start` to every vertex, or `None` where
/// there is no way. Lengths must not be negative.
pub fn dijkstra(graph: &[Vec<(usize, u32)>], start: usize) -> Vec<Option<u32>> {
    let mut best: Vec<Option<u32>> = vec![None; graph.len()];
    // A min-heap of (distance so far, vertex): the closest place comes out first.
    let mut heap = BinaryHeap::new();

    best[start] = Some(0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((dist, v))) = heap.pop() {
        // An older, longer entry for a vertex we have since reached faster.
        if best[v].is_some_and(|known| dist > known) {
            continue;
        }
        for &(w, length) in &graph[v] {
            let through_v = dist + length;
            // Found a shorter way to `w`? Remember it and queue it again.
            if best[w].is_none_or(|known| through_v < known) {
                best[w] = Some(through_v);
                heap.push(Reverse((through_v, w)));
            }
        }
    }
    best
}

Go through it in order.

• best holds the shortest distance found so far for each place. None means "no way found yet", so an unreachable place stays None to the end.
• The heap holds Reverse((distance, place)). Reverse flips the heap, so the smallest distance comes out first, exactly as in lesson 8.
• When we pop an entry, the first check skips stale ones: if dist is bigger than the known best for that place, a better entry was already handled.
• For each road out of v, through_v is the distance if we went by way of v. If that beats what we knew (or we knew nothing), record it, and push the new entry.
• When the heap is empty, best is the answer for every place.

Remember: only the pairs that improve something go onto the heap, and a stale pair is skipped when it comes out.

Rust has no shortest-path function in the standard library. (The petgraph crate has Dijkstra, if you need it in a project.) The useful pieces are the ones you met in lesson 8.

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

let mut heap = BinaryHeap::new();
heap.push(Reverse((8, 'D')));
heap.push(Reverse((2, 'C')));
heap.push(Reverse((5, 'B')));

// `Reverse` flips the heap, so the SMALLEST distance comes out first.
// Tuples compare their first part first, so the distance leads.
let Reverse((dist, place)) = heap.pop().unwrap();
println!("{} {}", dist, place);
assert_eq!((dist, place), (2, 'C'));

Two facts make Reverse((distance, place)) work.

• BinaryHeap is a max-heap by default, so it gives back the biggest first. Reverse flips the comparison, which turns it into a min-heap.
• A tuple compares its first part first, and only looks at the second part on a tie. So the distance decides the order, and the place just rides along.

Because Reverse and tuples already know how to compare themselves, the heap needs no extra code. Also notice the use of Option<u32> for distances instead of a huge number like u32::MAX standing for "unknown". With u32::MAX, adding a road length to "unknown" would overflow. None cannot be added to by mistake, and it reads as what it means.

Each road can add one entry to the heap, so the heap holds at most E entries, and each push or pop costs O(log E), which is O(log V) for any normal graph. If a graph has a negative road, neither BFS nor Dijkstra is right. A different algorithm, Bellman-Ford, handles that case, and it is slower.

Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn knight_moves(from: (usize, usize), to: (usize, usize)) -> usize {
    todo!("each square is a vertex; a knight's jump is an edge")
}

/// The fewest knight's jumps between two squares of an 8 by 8 board.
pub fn knight_moves(from: (usize, usize), to: (usize, usize)) -> usize {
    use std::collections::VecDeque;

    const JUMPS: [(isize, isize); 8] =
        [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)];

    let mut jumps = [[None; 8]; 8];
    jumps[from.0][from.1] = Some(0);
    let mut queue = VecDeque::from([from]);

    while let Some((r, c)) = queue.pop_front() {
        let here: usize = jumps[r][c].unwrap_or(0);
        if (r, c) == to {
            return here;
        }
        for (dr, dc) in JUMPS {
            let (Some(nr), Some(nc)) = (r.checked_add_signed(dr), c.checked_add_signed(dc)) else {
                continue;
            };
            if nr < 8 && nc < 8 && jumps[nr][nc].is_none() {
                jumps[nr][nc] = Some(here + 1);
                queue.push_back((nr, nc));
            }
        }
    }
    unreachable!("a knight can reach every square of an 8 by 8 board")
}

pub fn network_delay(n: usize, links: &[(usize, usize, u32)], source: usize) -> Option<u32> {
    todo!("when does the last place hear the news?")
}

/// Each link `(a, b, time)` carries a signal one way, from `a` to `b`.
/// Returns when the last place hears it, or `None` if someone never does.
pub fn network_delay(n: usize, links: &[(usize, usize, u32)], source: usize) -> Option<u32> {
    let mut graph = vec![Vec::new(); n];
    for &(a, b, time) in links {
        graph[a].push((b, time));
    }

    let times = dijkstra(&graph, source);
    // The news is complete when the slowest place has heard it.
    times.into_iter().try_fold(0, |slowest, time| Some(slowest.max(time?)))
}

pub fn easiest_hike(n: usize, trails: &[(usize, usize, u32)], from: usize, to: usize) -> Option<u32> {
    todo!("the path whose steepest trail is as gentle as possible")
}

/// The smallest possible "steepest trail" over all routes from `from` to
/// `to`. Trails go both ways, and each has a steepness.
pub fn easiest_hike(n: usize, trails: &[(usize, usize, u32)], from: usize, to: usize) -> Option<u32> {
    use std::cmp::Reverse;
    use std::collections::BinaryHeap;

    let mut graph = vec![Vec::new(); n];
    for &(a, b, steep) in trails {
        graph[a].push((b, steep));
        graph[b].push((a, steep));
    }

    // Same as Dijkstra, but a route costs its worst trail, not its total.
    let mut best: Vec<Option<u32>> = vec![None; n];
    let mut heap = BinaryHeap::new();
    best[from] = Some(0);
    heap.push(Reverse((0, from)));

    while let Some(Reverse((worst, v))) = heap.pop() {
        if v == to {
            return Some(worst);
        }
        if best[v].is_some_and(|known| worst > known) {
            continue;
        }
        for &(w, steep) in &graph[v] {
            let route_worst = worst.max(steep); // the only change from Dijkstra
            if best[w].is_none_or(|known| route_worst < known) {
                best[w] = Some(route_worst);
                heap.push(Reverse((route_worst, w)));
            }
        }
    }
    None
}

"Shortest" is a loaded word. The first thing a good answer does is pin down what it means.

• Spot the signals. "Fewest moves", "minimum steps", "cheapest route", "earliest time", and "least effort" all point here. A grid, a word puzzle, or a network can all be a graph underneath.
• Ask about the lengths. Say it out loud: "are all steps equal, or do they have costs?". Equal steps mean BFS. Costs of zero or more mean Dijkstra. A negative cost means you need another algorithm, and saying so scores well.
• Say why the greedy step is safe. "The closest unsettled place cannot be improved, because every other route goes through something further away." One sentence, and it shows you understand rather than recite.
• Name the data structure. "A min-heap of distance and place pairs." In Rust, that is a BinaryHeap of Reverse tuples.
• Mention stale entries. Saying "I skip an entry whose distance is worse than the best known" shows you have done it for real.
• State the cost. BFS is O(V + E). Dijkstra with a heap is O((V + E) log V).
• Rebuild the path when asked. If the question wants the route, not the length, keep a parent for each place and walk it back. Say that it costs one extra list.
• Reshape the cost. Problems like "minimise the worst step" are Dijkstra with max instead of +. Mentioning that you can swap the rule is a strong signal.

Made by VeraStack Labs