devLap

A Shortest-Path CLI in Rust — Making a Min-Heap from a Max-Heap, Path Reconstruction, and Rejecting Negative Weights

rust dev.to

A CLI that finds shortest paths in a weighted graph, in Rust, with Dijkstra's algorithm. Three implementation hinges: (1) Dijkstra needs a min-priority-queue to pull the closest unfinalized node, but Rust's BinaryHeap is a max-heap — so you reverse the Ord, (2) record predecessors to reconstruct the path, and (3) Dijkstra is wrong for negative weights, so reject them at parse time.

📦 GitHub: https://github.com/sen-ltd/dijkstra-cli

(It's a CLI — no live demo. Run with cargo run or Docker.)

Input format

Edge list, one per line: FROM TO WEIGHT. # comments and blanks ignored. --undirected mirrors every edge.

A B 7
A C 9
C F 2
F E 9
Enter fullscreen mode Exit fullscreen mode

Hinge 1: a min-heap from a max-heap

Dijkstra repeatedly takes the node closest to the source — a min-priority-queue. But Rust's std::collections::BinaryHeap is a max-heap (largest on top).

The fix is to reverse the Ord of the State you push, so popping yields the minimum distance:

#[derive(Copy, Clone, Eq, PartialEq)]
struct State { dist: u64, idx: usize }

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        // reverse both keys: smallest dist pops first; on a tie, smaller idx
        other.dist.cmp(&self.dist).then_with(|| other.idx.cmp(&self.idx))
    }
}
impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}
Enter fullscreen mode Exit fullscreen mode

other.dist.cmp(&self.dist) flips the comparison, using the max-heap as a min-heap — the canonical Rust idiom (the std-doc Dijkstra example does this too).

Reversing the secondary key (idx) too makes ties deterministic. Without it, equal-distance nodes pop in an arbitrary order and the reconstructed path wobbles between runs. Pinned by a test:

#[test]
fn deterministic_path_on_ties() {
    // A->B->D and A->C->D cost the same; predecessor is the smaller, B
    let sp = dijkstra(&g("A B 1\nA C 1\nB D 1\nC D 1\n"), "A");
    assert_eq!(sp.path_to("D").unwrap(), vec!["A", "B", "D"]);
}
Enter fullscreen mode Exit fullscreen mode

I actually wrote this test first without reversing idx — it returned A->C->D and failed. Testing determinism caught the bug in my own Ord.

Hinge 2: discard stale heap entries

You want "found a shorter distance? update the queue," but BinaryHeap has no decrease-key. The fix: push duplicates and skip stale pops (lazy deletion):

while let Some(State { dist, idx }) = heap.pop() {
    if dist > best[idx] {
        continue; // a shorter distance was already finalized — stale entry
    }
    // ... relax neighbors ...
}
Enter fullscreen mode Exit fullscreen mode

If dist > best[idx], a shorter path was found after this entry was pushed, so ignore it. Simpler than a hand-rolled indexed heap, and still O((V+E) log V).

#[test]
fn stale_heap_entries_ignored() {
    // direct B is 10 but via C it's 2
    let sp = dijkstra(&g("A B 10\nA C 1\nC B 1\n"), "A");
    assert_eq!(sp.dist["B"], 2);
    assert_eq!(sp.path_to("B").unwrap(), vec!["A", "C", "B"]);
}
Enter fullscreen mode Exit fullscreen mode

Hinge 3: path reconstruction & negative weights

You want the path, not just the distance. Each relaxation records "who updated this node" in a prev map; path_to walks it back from the target and reverses.

And Dijkstra is incorrect for negative weights — the assumption that a finalized node can't later be improved breaks. Reject them at parse time:

if w < 0 {
    return Err(GraphError::NegativeWeight(line, w));
}
Enter fullscreen mode Exit fullscreen mode

The error tells you to use Bellman-Ford instead of silently returning a wrong answer:

$ echo "A B -3" | dijkstra A
error: line 1: negative weight -3 — Dijkstra requires non-negative weights
Enter fullscreen mode Exit fullscreen mode

CLI 

match &cli.target {
    Some(target) => { /* print the single path */ }
    None => { /* table of shortest distances to all reachable nodes */ }
}
Enter fullscreen mode Exit fullscreen mode

With a target, one path; without, all distances + paths. stdin supported.

$ dijkstra A E --file examples/graph.txt
A -> C -> F -> E  (distance 20)
Enter fullscreen mode Exit fullscreen mode

A test pins the classic Wikipedia Dijkstra graph: A→E is A->C->F->E = 9+2+9 = 20.

Architecture 

src/graph.rs — edge-list parse, Dijkstra (BinaryHeap), path reconstruction
src/main.rs  — clap CLI: single path or all-distances table, file/stdin
Enter fullscreen mode Exit fullscreen mode

Single clap dependency; 10 inline tests in graph.rs. Docker: rust:1.85-alpine → alpine, non-root. House style (committed Cargo.lock, opt-level="z" + LTO).

Run it 

cargo test
cargo run -- A E --file examples/graph.txt
docker build -t dijkstra . && docker run --rm -i dijkstra A E < examples/graph.txt
Enter fullscreen mode Exit fullscreen mode

Takeaways

  • Rust's BinaryHeap is a max-heap; reverse State's Ord to use it as the min-heap Dijkstra needs.
  • Reverse the secondary key too for deterministic ties — stable path reconstruction (a test caught this).
  • Skip stale entries on pop instead of decrease-key (lazy deletion); still O((V+E) log V).
  • Reconstruct the path from a prev predecessor map.
  • Reject negative weights — Dijkstra's invariant breaks, so error instead of returning garbage.

This is OSS portfolio #272 from SEN LLC (Tokyo). https://sen.ltd/portfolio/

Source: dev.to

arrow_back Back to Tutorials