oxicuda_graphalg/shortest_path/
dijkstra.rs

1//! Binary-heap Dijkstra single-source shortest path. Rejects negative weights.
2
3use std::cmp::Ordering;
4use std::collections::BinaryHeap;
5
6use crate::error::{GraphalgError, GraphalgResult};
7use crate::repr::weighted_graph::WeightedGraph;
8
9/// Result of a Dijkstra run from a single source.
10#[derive(Debug, Clone)]
11pub struct DijkstraOutput {
12    pub dist: Vec<f64>,
13    pub parent: Vec<usize>,
14}
15
16#[derive(Debug, Clone, Copy, PartialEq)]
17struct HeapItem {
18    dist: f64,
19    node: usize,
20}
21
22impl Eq for HeapItem {}
23impl PartialOrd for HeapItem {
24    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
25        Some(self.cmp(other))
26    }
27}
28impl Ord for HeapItem {
29    fn cmp(&self, other: &Self) -> Ordering {
30        // Min-heap by distance.
31        other
32            .dist
33            .partial_cmp(&self.dist)
34            .unwrap_or(Ordering::Equal)
35            .then_with(|| other.node.cmp(&self.node))
36    }
37}
38
39pub fn dijkstra(g: &WeightedGraph, source: usize) -> GraphalgResult<DijkstraOutput> {
40    if source >= g.n {
41        return Err(GraphalgError::SourceOutOfRange {
42            node: source,
43            n: g.n,
44        });
45    }
46    let mut dist = vec![f64::INFINITY; g.n];
47    let mut parent = vec![usize::MAX; g.n];
48    dist[source] = 0.0;
49    parent[source] = source;
50    let mut heap: BinaryHeap<HeapItem> = BinaryHeap::new();
51    heap.push(HeapItem {
52        dist: 0.0,
53        node: source,
54    });
55    while let Some(HeapItem { dist: d, node: u }) = heap.pop() {
56        if d > dist[u] {
57            continue;
58        }
59        for &(v, w) in g.neighbors(u)? {
60            if w < 0.0 {
61                return Err(GraphalgError::NegativeWeight {
62                    edge: (u, v),
63                    weight: w,
64                });
65            }
66            let nd = d + w;
67            if nd < dist[v] {
68                dist[v] = nd;
69                parent[v] = u;
70                heap.push(HeapItem { dist: nd, node: v });
71            }
72        }
73    }
74    Ok(DijkstraOutput { dist, parent })
75}
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn dijkstra_4node() {
83        // 0 -> 1 (1), 0 -> 2 (4), 1 -> 2 (2), 1 -> 3 (5), 2 -> 3 (1)
84        let mut g = WeightedGraph::new(4);
85        g.add_edge(0, 1, 1.0).expect("ok");
86        g.add_edge(0, 2, 4.0).expect("ok");
87        g.add_edge(1, 2, 2.0).expect("ok");
88        g.add_edge(1, 3, 5.0).expect("ok");
89        g.add_edge(2, 3, 1.0).expect("ok");
90        let out = dijkstra(&g, 0).expect("ok");
91        assert!((out.dist[3] - 4.0).abs() < 1e-12);
92    }
93
94    #[test]
95    fn dijkstra_rejects_negative() {
96        let mut g = WeightedGraph::new(2);
97        g.add_edge(0, 1, -1.0).expect("ok");
98        assert!(dijkstra(&g, 0).is_err());
99    }
100
101    #[test]
102    fn dijkstra_zero_weight_ok() {
103        let mut g = WeightedGraph::new(2);
104        g.add_edge(0, 1, 0.0).expect("ok");
105        let out = dijkstra(&g, 0).expect("ok");
106        assert!((out.dist[1] - 0.0).abs() < 1e-12);
107    }
108}
oxicuda_graphalg/shortest_path/dijkstra.rs

oxicuda_graphalg/shortest_path/
dijkstra.rs
