graaf/algo/
dijkstra.rs

1//! Dijkstra's algorithm.
2//!
3//! Dijkstra's algorithm with binary heap finds the shortest path in an
4//! arc-weighted digraph.[^1]
5//!
6//! The time complexity is `O(v log v + a)`, where `v` is the digraph's order
7//! and `a` is the digraph's size.
8//!
9//! # Examples
10//!
11//! ## Single source
12//!
13//! The path from vertex `0` is red. `t` denotes the iteration indices.
14//!
15//! ![A digraph and the shortest path from source vertex `0` obtained by Dijkstra's algorithm](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/dijkstra_1-0.87.4.svg?)
16//!
17//! ```
18//! use {
19//!     graaf::{
20//!         AddArcWeighted,
21//!         AdjacencyListWeighted,
22//!         Dijkstra,
23//!         Empty,
24//!     },
25//!     std::iter::once,
26//! };
27//!
28//! let mut digraph = AdjacencyListWeighted::<usize>::empty(7);
29//!
30//! digraph.add_arc_weighted(0, 1, 1);
31//! digraph.add_arc_weighted(1, 2, 1);
32//! digraph.add_arc_weighted(1, 6, 6);
33//! digraph.add_arc_weighted(2, 4, 1);
34//! digraph.add_arc_weighted(3, 0, 2);
35//! digraph.add_arc_weighted(4, 5, 2);
36//! digraph.add_arc_weighted(5, 6, 1);
37//!
38//! let mut dijkstra = Dijkstra::new(&digraph, once(0));
39//!
40//! assert!(dijkstra.eq([0, 1, 2, 4, 5, 6]));
41//! ```
42//!
43//! ## Multiple sources
44//!
45//! The path from vertex `0` is red. The path from vertex `3` is blue.
46//!
47//! ![A digraph and the shortest path from two source vertices obtained by Dijkstra's algorithm](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/dijkstra_multi_source_1-0.87.4.svg?)
48//!
49//! ```
50//! use graaf::{
51//!     AddArcWeighted,
52//!     AdjacencyListWeighted,
53//!     Dijkstra,
54//!     Empty,
55//! };
56//!
57//! let mut digraph = AdjacencyListWeighted::<usize>::empty(7);
58//!
59//! digraph.add_arc_weighted(0, 1, 1);
60//! digraph.add_arc_weighted(1, 2, 1);
61//! digraph.add_arc_weighted(1, 6, 5);
62//! digraph.add_arc_weighted(2, 4, 1);
63//! digraph.add_arc_weighted(3, 0, 2);
64//! digraph.add_arc_weighted(3, 5, 1);
65//! digraph.add_arc_weighted(4, 5, 1);
66//! digraph.add_arc_weighted(5, 6, 3);
67//!
68//! let mut dijkstra = Dijkstra::new(&digraph, [0, 3].into_iter());
69//!
70//! assert!(dijkstra.eq([3, 0, 5, 1, 2, 4, 6]));
71//! ```
72//!
73//! [^1]: Edsger Wybe Dijkstra. 1959. A note on two problems in connexion with
74//!   graphs. Numer. Math. 1, 1 (December 1959), 269–271.
75//!   <https://doi.org/10.1007/BF01386390>
76
77use {
78    crate::{
79        Order,
80        OutNeighborsWeighted,
81    },
82    core::cmp::Reverse,
83    std::collections::BinaryHeap,
84};
85
86/// Dijkstra's algorithm.
87///
88/// # Examples
89///
90/// ## Single source
91///
92/// The path from vertex `0` is red. `t` denotes the iteration indices.
93///
94/// ![A digraph and the shortest path from source vertex `0` obtained by Dijkstra's algorithm](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/dijkstra_1-0.87.4.svg?)
95///
96/// ```
97/// use {
98///     graaf::{
99///         AddArcWeighted,
100///         AdjacencyListWeighted,
101///         Dijkstra,
102///         Empty,
103///     },
104///     std::iter::once,
105/// };
106///
107/// let mut digraph = AdjacencyListWeighted::<usize>::empty(7);
108///
109/// digraph.add_arc_weighted(0, 1, 1);
110/// digraph.add_arc_weighted(1, 2, 1);
111/// digraph.add_arc_weighted(1, 6, 6);
112/// digraph.add_arc_weighted(2, 4, 1);
113/// digraph.add_arc_weighted(3, 0, 2);
114/// digraph.add_arc_weighted(4, 5, 2);
115/// digraph.add_arc_weighted(5, 6, 1);
116///
117/// let mut dijkstra = Dijkstra::new(&digraph, once(0));
118///
119/// assert!(dijkstra.eq([0, 1, 2, 4, 5, 6]));
120/// ```
121///
122/// ## Multiple sources
123///
124/// The path from vertex `0` is red. The path from vertex `3` is blue.
125///
126/// ![A digraph and the shortest path from two source vertices obtained by Dijkstra's algorithm](https://raw.githubusercontent.com/bsdrks/graaf-images/main/out/dijkstra_multi_source_1-0.87.4.svg?)
127///
128/// ```
129/// use graaf::{
130///     AddArcWeighted,
131///     AdjacencyListWeighted,
132///     Dijkstra,
133///     Empty,
134/// };
135///
136/// let mut digraph = AdjacencyListWeighted::<usize>::empty(7);
137///
138/// digraph.add_arc_weighted(0, 1, 1);
139/// digraph.add_arc_weighted(1, 2, 1);
140/// digraph.add_arc_weighted(1, 6, 5);
141/// digraph.add_arc_weighted(2, 4, 1);
142/// digraph.add_arc_weighted(3, 0, 2);
143/// digraph.add_arc_weighted(3, 5, 1);
144/// digraph.add_arc_weighted(4, 5, 1);
145/// digraph.add_arc_weighted(5, 6, 3);
146///
147/// let mut dijkstra = Dijkstra::new(&digraph, [0, 3].into_iter());
148///
149/// assert!(dijkstra.eq([3, 0, 5, 1, 2, 4, 6]));
150/// ```
151#[derive(Clone, Debug)]
152pub struct Dijkstra<'a, D> {
153    digraph: &'a D,
154    dist: Vec<usize>,
155    heap: BinaryHeap<(Reverse<usize>, usize)>,
156}
157
158impl<'a, D> Dijkstra<'a, D>
159where
160    D: Order,
161{
162    /// Initialize Dijkstra's algorithm.
163    ///
164    /// # Arguments
165    ///
166    /// * `digraph`: The digraph.
167    /// * `sources`: The source vertices.
168    #[must_use]
169    pub fn new<T>(digraph: &'a D, sources: T) -> Self
170    where
171        D: Order,
172        T: Iterator<Item = usize> + Clone,
173    {
174        let order = digraph.order();
175        let mut dist = vec![usize::MAX; order];
176        let mut heap = BinaryHeap::with_capacity(order);
177        let dist_ptr = dist.as_mut_ptr();
178
179        for u in sources {
180            unsafe { *dist_ptr.add(u) = 0 };
181
182            heap.push((Reverse(0), u));
183        }
184
185        Self {
186            digraph,
187            dist,
188            heap,
189        }
190    }
191}
192
193impl<D> Iterator for Dijkstra<'_, D>
194where
195    D: Order + OutNeighborsWeighted<Weight = usize>,
196{
197    type Item = usize;
198
199    fn next(&mut self) -> Option<Self::Item> {
200        let (Reverse(w_prev), u) = self.heap.pop()?;
201        let dist_ptr = self.dist.as_mut_ptr();
202
203        for (v, w) in self.digraph.out_neighbors_weighted(u) {
204            let w_next = w + w_prev;
205            let dist_v = unsafe { dist_ptr.add(v) };
206
207            unsafe {
208                if w_next < *dist_v {
209                    *dist_v = w_next;
210
211                    self.heap.push((Reverse(w_next), v));
212                }
213            }
214        }
215
216        if unsafe { *dist_ptr.add(u) } == w_prev {
217            return Some(u);
218        }
219
220        None
221    }
222}
223
224#[cfg(test)]
225mod tests {
226    use {
227        super::*,
228        crate::repr::adjacency_list_weighted::fixture::{
229            bang_jensen_94_usize,
230            bang_jensen_96_usize,
231            kattis_bryr_1_usize,
232            kattis_bryr_2_usize,
233            kattis_bryr_3_usize,
234            kattis_crosscountry_usize,
235            kattis_shortestpath1_usize,
236        },
237        std::iter::once,
238    };
239
240    #[test]
241    fn iter_bang_jensen_94() {
242        let digraph = bang_jensen_94_usize();
243
244        assert!(Dijkstra::new(&digraph, once(0)).eq([0, 2, 1, 5, 4, 3, 6]));
245    }
246
247    #[test]
248    fn iter_bang_jensen_96() {
249        let digraph = bang_jensen_96_usize();
250
251        assert!(Dijkstra::new(&digraph, once(0)).eq([0, 2, 4, 1, 3, 5]));
252    }
253
254    #[test]
255    fn iter_kattis_bryr_1() {
256        let digraph = kattis_bryr_1_usize();
257
258        assert!(Dijkstra::new(&digraph, once(0)).eq([0, 2, 1]));
259    }
260
261    #[test]
262    fn iter_kattis_bryr_2() {
263        let digraph = kattis_bryr_2_usize();
264
265        assert!(Dijkstra::new(&digraph, once(0)).eq([0, 3, 1, 4, 2, 5]));
266    }
267
268    #[test]
269    fn iter_kattis_bryr_3() {
270        let digraph = kattis_bryr_3_usize();
271
272        assert!(
273            Dijkstra::new(&digraph, once(0))
274                .eq([0, 3, 7, 5, 8, 4, 1, 9, 6, 2])
275        );
276    }
277
278    #[test]
279    fn iter_kattis_crosscountry() {
280        let digraph = kattis_crosscountry_usize();
281
282        assert!(Dijkstra::new(&digraph, once(0)).eq([0, 1, 2, 3]));
283    }
284
285    #[test]
286    fn iter_kattis_shortestpath1() {
287        let digraph = kattis_shortestpath1_usize();
288
289        assert!(Dijkstra::new(&digraph, once(0)).eq([0, 1, 2]));
290    }
291}
graaf/algo/dijkstra.rs

graaf/algo/
dijkstra.rs
