Problem overview
The function dijkstra receives n, the number of vertices (labeled 0 to n - 1), and a vector of weighted edges. Each edge is a triple [u, v, weight] joining two vertices in both directions, and every weight is at least 1. The graph is connected. The function returns a vector dist where dist[i] is the length of the shortest path from vertex 0 to vertex i, measured as the sum of the weights along the path.
For n = 5 and edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]] the answer is [0, 3, 1, 4, 7]. The direct edge from 0 to 1 costs 4, but going through vertex 2 costs only 1 + 2 = 3. Vertex 3 is then reached through 1 at cost 4, which beats the direct route through 2 at cost 1 + 5 = 6, and vertex 4 follows at cost 4 + 3 = 7.
Approach: always expand the closest unfinished vertex
When every edge costs the same, a queue finds shortest paths, as in BFS. With weights, the fewest edges is no longer the cheapest path, so the order of exploration has to follow distance instead of edge count.
Dijkstra's algorithm keeps the best distance found so far for every vertex and repeatedly expands the vertex with the smallest distance that has not been finished. Because all weights are positive, no later path can reach that vertex more cheaply than the best known one: any other route has to leave through a vertex that is at least as far away, and then add more positive weight. So its distance is final when it comes out first.
Expanding a vertex means relaxing its edges. For each neighbor v with edge weight w, the path through the current vertex u costs dist[u] + w. If that beats dist[v], the better distance is recorded.
A binary heap (a priority queue) hands out the smallest distance quickly. It can't change an entry in place, so the algorithm uses lazy deletion: when a distance improves, a new entry is pushed and the old one stays in the heap. When an old entry finally comes out with a distance worse than the current dist, it is stale and is skipped.
On the example: vertex 0 gives vertex 1 a distance of 4 and vertex 2 a distance of 1. Vertex 2 comes out next and improves vertex 1 to 3, and gives vertex 3 a distance of 6. The entry for vertex 1 at distance 3 comes out before the stale entry at distance 4, and improves vertex 3 to 4. The stale entries at distances 4 for vertex 1 and 6 for vertex 3 are skipped when they come out. Vertex 3 gives vertex 4 its distance of 7.
Step by step
- Shadow
nas ausizeso it can size and index vectors, then createadj, a vector ofnempty neighbor lists. Each entry will be a pair of the neighbor and the weight. - Fill the lists. For each edge in
&edges, convert the endpoints tousizeand push(v, w)ontoadj[u]and(u, w)ontoadj[v], since the graph is undirected. - Create
distfilled withi32::MAX, meaning "not reached", and setdist[0]to 0. - Create the heap. Rust's
BinaryHeapis a max-heap, so wrap the entries inReverseto get a min-heap. Push the source asReverse((0, 0)): distance first, then vertex, so entries order by distance. - Loop with
while letoverheap.pop(), destructuring the entry intodandu. Skip it withcontinueifd > dist[u], because that entry is stale. - Loop over
&adj[u]with the pattern&(v, w), so every outgoing edge is considered. - Relax each edge. Compute
nd = dist[u] + w. Whennd < dist[v], store it and pushReverse((nd, v)). Pushing only on a real improvement keeps the heap small. - Return
dist. Once the heap is empty every distance is final.
The solution in Rust
impl Solution {
fn dijkstra(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let mut adj: Vec<Vec<(usize, i32)>> = vec![vec![]; n];
for e in &edges {
let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
adj[u].push((v, w));
adj[v].push((u, w));
}
let mut dist = vec![i32::MAX; n];
dist[0] = 0;
let mut heap = std::collections::BinaryHeap::new();
heap.push(std::cmp::Reverse((0i32, 0usize)));
while let Some(std::cmp::Reverse((d, u))) = heap.pop() {
if d > dist[u] {
continue;
}
for &(v, w) in &adj[u] {
let nd = dist[u] + w;
if nd < dist[v] {
dist[v] = nd;
heap.push(std::cmp::Reverse((nd, v)));
}
}
}
dist
}
}
The Rust details worth a closer look:
- Max-heap by default.
BinaryHeap::popreturns the largest element. After pushing 3, 9 and 1 it returns 9. With each value wrapped inReverse, the order flips andpopreturnsReverse(1), the smallest. - Tuple ordering. Tuples compare field by field, so
Reverse((nd, v))orders first by distance and uses the vertex only to break ties. That is why the distance is the first element. - Destructuring
Reverse.Some(std::cmp::Reverse((d, u)))is a pattern: it unwraps theOption, then theReversewrapper, then the tuple.popreturnsNonewhen the heap is empty, which ends the loop. - Inferred heap type.
BinaryHeap::new()gets its element type from the firstpush. The suffixes in(0i32, 0usize)fix the types of the two numbers. - Why
i32::MAXis safe. Only reached vertices enter the heap, sodist[u]is neveri32::MAXwhendist[u] + wis computed, and the sum can't overflow. With the limits of this lesson (at most 999 edges on a path, each at most 1000) distances stay far below the maximum. vec![vec![]; n]works because the annotation onadjtells Rust the inner type, and the inner empty vector is clonedntimes.- The pattern
&(v, w)copies the two numbers out of the borrowed tuple, sovandware plain values.
Complexity
Time: O((n + m) log m), where m is the number of edges. Each edge can cause at most one push per direction, so the heap sees at most 2m + 1 entries, and each push or pop costs O(log m). Stale entries are popped and skipped in constant time.
Space: O(n + m). The adjacency lists store 2m pairs, dist has n entries, and the heap holds at most 2m + 1 entries.
Edge cases and common mistakes
- Forgetting
Reverse. Without it the heap hands out the farthest vertex first. Because distances are only ever lowered, the final values can still come out right, but the guarantee that a popped vertex is final is lost and the work can grow enormously. - Skipping the stale check. Without
if d > dist[u] { continue; }the answer stays correct, but outdated entries get expanded and the work can grow a lot. - Adding only one direction of each edge. The graph is undirected: for
n = 2andedges = [[1,0,7]], the answer[0, 7]needs the edge to be usable from vertex 0. - Negative weights. The reasoning that a popped vertex is final needs weights that are not negative. This lesson guarantees weights of at least 1.
- Unreachable vertices. The lesson's graphs are connected. In a graph that isn't, such as
n = 3withedges = [[0,1,1]], vertex 2 keeps the valuei32::MAX, which is 2147483647. - Pushing on every relaxation attempt. Pushing without the
nd < dist[v]test fills the heap with useless entries.
Testing
n = 5,edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]gives[0, 3, 1, 4, 7].n = 2,edges = [[1,0,7]]gives[0, 7].n = 3,edges = [[0,1,1]]gives[0, 1, 2147483647](vertex 2 is unreachable).
