dijkstra/
lib.rs

1//! Dijkstra's single-source shortest path on a weighted graph.
2//!
3//! Given a directed or undirected graph with non-negative edge weights,
4//! Dijkstra's algorithm computes the shortest distance from a source
5//! vertex to every other reachable vertex in `O((V + E) log V)` time
6//! using a binary heap.
7//!
8//! This module exposes a single function [`dijkstra`] that takes the
9//! adjacency list as `&[Vec<(usize, u64)>]` (each edge is `(neighbor,
10//! weight)`) and returns a `HashMap<usize, u64>` of minimum distances.
11
12use std::cmp::Reverse;
13use std::collections::{BinaryHeap, HashMap};
14
15/// Compute shortest distances from `source` to every reachable vertex.
16///
17/// `graph[u]` is the list of edges leaving `u`: pairs `(v, w)` meaning
18/// there is an edge to `v` with weight `w`. Returns a map from vertex
19/// id to minimum distance. Unreachable vertices are absent.
20///
21/// # Panics
22///
23/// Panics if `source >= graph.len()`.
24pub fn dijkstra(graph: &[Vec<(usize, u64)>], source: usize) -> HashMap<usize, u64> {
25    assert!(source < graph.len(), "source vertex out of range");
26    let mut dist: HashMap<usize, u64> = HashMap::new();
27    let mut heap: BinaryHeap<Reverse<(u64, usize)>> = BinaryHeap::new();
28    dist.insert(source, 0);
29    heap.push(Reverse((0, source)));
30    while let Some(Reverse((d, u))) = heap.pop() {
31        if d > dist[&u] {
32            continue; // stale entry
33        }
34        for &(v, w) in &graph[u] {
35            let nd = d + w;
36            let is_better = match dist.get(&v) {
37                None => true,
38                Some(cur) => nd < *cur,
39            };
40            if is_better {
41                dist.insert(v, nd);
42                heap.push(Reverse((nd, v)));
43            }
44        }
45    }
46    dist
47}
dijkstra/lib.rs

dijkstra/
lib.rs
