graph_shortest_path/
dijkstra.rs

1use graph_core::{Graph, GraphError, NodeId};
2use ordered_float::OrderedFloat;
3use std::cmp::Reverse;
4use std::collections::{BinaryHeap, HashMap};
5
6/// Result of a Dijkstra shortest-path search from one source node.
7///
8/// Contains shortest distances from the source and the parent map needed
9/// to reconstruct any shortest path via [`reconstruct_path`].
10///
11/// [`reconstruct_path`]: crate::dijkstra::reconstruct_path
12pub struct DijkstraResult {
13    /// Map from `NodeId` to the shortest distance from the source.
14    ///
15    /// Only nodes reachable from the source have an entry. Unreachable
16    /// nodes are absent (not `f64::INFINITY`).
17    pub distances: HashMap<NodeId, f64>,
18    /// Parent of each node in the shortest-path tree.
19    ///
20    /// Follow `parents[v] → parents[parents[v]] → … → source` to recover
21    /// the shortest path. The source itself has no parent entry.
22    pub parents: HashMap<NodeId, NodeId>,
23}
24
25/// Runs Dijkstra's algorithm from `source` and returns shortest distances and
26/// the parent map.
27///
28/// Requires all edge weights to be **non-negative**. Negative weights will
29/// produce incorrect results without error (use [`bellman_ford`] instead).
30///
31/// Uses a binary min-heap (`BinaryHeap<Reverse<…>>`) with lazy deletion:
32/// stale (distance, node) entries are skipped rather than updated in place.
33///
34/// # Errors
35///
36/// Returns [`GraphError::NodeNotFound`] if `source` is not in the graph.
37///
38/// # Complexity
39///
40/// O((V + E) log V) with a binary heap.
41///
42/// # Examples
43///
44/// ```
45/// use graph_core::{AdjacencyList, Graph};
46/// use graph_shortest_path::dijkstra;
47///
48/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
49/// let a = g.add_node(());
50/// let b = g.add_node(());
51/// let c = g.add_node(());
52/// g.add_edge(a, b, 1.0).unwrap();
53/// g.add_edge(b, c, 2.0).unwrap();
54/// g.add_edge(a, c, 10.0).unwrap();
55///
56/// let result = dijkstra(&g, a).unwrap();
57/// assert_eq!(result.distances[&c], 3.0); // a→b→c is cheaper than a→c
58/// assert_eq!(result.parents[&c], b);
59/// ```
60///
61/// [`bellman_ford`]: crate::bellman_ford::bellman_ford
62pub fn dijkstra<G>(graph: &G, source: NodeId) -> Result<DijkstraResult, GraphError>
63where
64    G: Graph<Weight = f64>,
65{
66    if !graph.contains_node(source) {
67        return Err(GraphError::NodeNotFound(source));
68    }
69
70    let mut distances: HashMap<NodeId, f64> = HashMap::new();
71    let mut parents: HashMap<NodeId, NodeId> = HashMap::new();
72
73    // Min-heap of (distance, node). `Reverse` makes BinaryHeap a min-heap.
74    // OrderedFloat gives us `Ord` on f64 (NaN is treated as largest).
75    let mut heap: BinaryHeap<Reverse<(OrderedFloat<f64>, NodeId)>> = BinaryHeap::new();
76
77    distances.insert(source, 0.0);
78    heap.push(Reverse((OrderedFloat(0.0), source)));
79
80    while let Some(Reverse((OrderedFloat(dist), node))) = heap.pop() {
81        // Lazy deletion: if we have already found a shorter path, skip this entry.
82        if let Some(&best) = distances.get(&node) {
83            if dist > best {
84                continue;
85            }
86        }
87
88        for (neighbour, &weight) in graph.neighbors(node) {
89            let candidate = dist + weight;
90            let current_best = distances.get(&neighbour).copied().unwrap_or(f64::INFINITY);
91
92            if candidate < current_best {
93                distances.insert(neighbour, candidate);
94                parents.insert(neighbour, node);
95                heap.push(Reverse((OrderedFloat(candidate), neighbour)));
96            }
97        }
98    }
99
100    Ok(DijkstraResult { distances, parents })
101}
102
103/// Reconstructs the shortest path from `start` to `end` using the parent map
104/// produced by [`dijkstra`].
105///
106/// Returns `Some((path, total_distance))` where `path[0] == start` and
107/// `path.last() == end`, or `None` if `end` is unreachable from `start`.
108///
109/// # Examples
110///
111/// ```
112/// use graph_core::{AdjacencyList, Graph};
113/// use graph_shortest_path::dijkstra;
114/// use graph_shortest_path::dijkstra::reconstruct_path;
115///
116/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
117/// let a = g.add_node(());
118/// let b = g.add_node(());
119/// let c = g.add_node(());
120/// g.add_edge(a, b, 1.0).unwrap();
121/// g.add_edge(b, c, 2.0).unwrap();
122///
123/// let result = dijkstra(&g, a).unwrap();
124/// let (path, dist) = reconstruct_path(&result, a, c).unwrap();
125/// assert_eq!(path, vec![a, b, c]);
126/// assert_eq!(dist, 3.0);
127/// ```
128pub fn reconstruct_path(
129    result: &DijkstraResult,
130    start: NodeId,
131    end: NodeId,
132) -> Option<(Vec<NodeId>, f64)> {
133    if start == end {
134        let dist = *result.distances.get(&start)?;
135        return Some((vec![start], dist));
136    }
137
138    // Check end is reachable.
139    let total_dist = *result.distances.get(&end)?;
140
141    let mut path = vec![end];
142    let mut current = end;
143
144    loop {
145        let prev = *result.parents.get(&current)?;
146        path.push(prev);
147        if prev == start {
148            break;
149        }
150        current = prev;
151    }
152
153    path.reverse();
154    Some((path, total_dist))
155}
graph_shortest_path/dijkstra.rs

graph_shortest_path/
dijkstra.rs
