Ace the Rust Interview

Enter your book access code

The curriculum, drills, tutor, and interviewer mode are for readers of Ace the Rust Interview. The code is printed in the Preface (Companion site access).

Don’t have the book yet? The landing page stays open — purchase unlocks this gym.

intermediate · order 132

Dijkstra with stale-entry skip

graph-dijkstra-01Related book chapters: 21 (optional — this page is complete on its own)Dijkstra

Slug: graph-dijkstra-01 · Paired reading: Chapter 21

Prompt

Weighted directed graph as Vec<Vec<(usize, u64)>> (neighbor, weight). fn dijkstra(g: &[Vec<(usize, u64)>], src: usize) -> Vec<u64> — distances (u64::MAX if unreachable). BinaryHeap of Reverse<(dist, node)>; skip stale heap entries.

Contract

  • Distances from src; unreachable nodes → u64::MAX
  • Empty outgoing adjacency is allowed; src distance is 0
  • Stale binary-heap entries must be skipped (shorter path wins)