algorithms_edu/algo/graph/shortest_path/
dijkstra.rs

1//! This mod contains an implementation of Dijkstra's shortest path algorithm from a start node to a
2//! specific ending node. Dijkstra can also be modified to find the shortest path between a starting
3//! node and all other nodes in the graph. However, in this implementation since we're only going
4//! from a starting node to an ending node we can employ an optimization to stop early once we've
5//! visited all the neighbors of the ending node.
6//!
7//! # Resources
8//!
9//! - [W. Fiset's video](https://www.youtube.com/watch?v=pSqmAO-m7Lk&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=18)
10
11use crate::algo::graph::{Edge, WeightedAdjacencyList};
12use ordered_float::OrderedFloat;
13use priority_queue::PriorityQueue;
14
15impl WeightedAdjacencyList {
16    pub fn dijkstra(&self, start: usize, end: usize) -> Option<(f64, Vec<usize>)> {
17        let n = self.node_count();
18        let mut dists = vec![f64::INFINITY; n];
19        let mut prev = vec![None; n];
20        let mut vis = vec![false; n];
21        let mut pq = PriorityQueue::with_capacity(self.node_count());
22        // `priority_queue::PriorityQueue` requires that the priority implements `Ord`,
23        // but the std floats implement only `PartialOrd`
24        pq.push(start, OrderedFloat::from(-0f64));
25        dists[start] = 0f64;
26        while let Some((node, cur_dist)) = pq.pop() {
27            // Once we've visited all the nodes spanning from the end
28            // node we know we can return the minimum distance value to
29            // the end node because it cannot get any better after this point.
30            if node == end {
31                break;
32            };
33            // `priority_queue::PriorityQueue` is a max priority queue, but we want the min.
34            // Negating the priority (dist) immediately before pushing and after popping will do.
35            let cur_dist = -cur_dist.into_inner();
36
37            vis[node] = true;
38
39            let dist = &mut dists[node];
40
41            // We already found a better path before we got to
42            // processing this node so we can ignore it.
43            if *dist < cur_dist {
44                continue;
45            }
46            *dist = cur_dist;
47            for &Edge { to, weight } in &self[node] {
48                // You cannot get a shorter path by revisiting
49                // a node you have already visited before.
50                if !vis[to] {
51                    // Relax edge by updating minimum cost if applicable.
52                    let new_dist = cur_dist + weight;
53                    if new_dist < dists[to] {
54                        prev[to] = Some(node);
55                        dists[to] = new_dist;
56                        pq.push(to, (-new_dist).into());
57                    }
58                }
59            }
60        }
61
62        if prev[end].is_none() {
63            if start == end {
64                Some((dists[start], vec![start]))
65            } else {
66                None
67            }
68        } else {
69            // reconstruct path
70            let mut path = vec![end];
71            let mut i = end;
72            while let Some(node) = prev[i] {
73                path.push(node);
74                i = node;
75            }
76            path.reverse();
77            Some((dists[end], path))
78        }
79    }
80}
81#[cfg(test)]
82mod tests {
83
84    use super::*;
85    #[test]
86    fn test_dijkstra() {
87        // example from https://www.youtube.com/watch?v=pSqmAO-m7Lk&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=18
88        // at 16:47
89        let graph = WeightedAdjacencyList::new_directed(
90            6,
91            &[
92                (0, 1, 5.),
93                (0, 2, 1.),
94                (1, 2, 2.),
95                (2, 1, 3.),
96                (1, 3, 3.),
97                (1, 4, 20.),
98                (2, 4, 12.),
99                (3, 2, 3.),
100                (3, 4, 2.),
101                (3, 5, 6.),
102                (3, 4, 2.),
103                (4, 5, 1.),
104            ],
105        );
106        let (dist, path) = graph.dijkstra(0, 5).unwrap();
107        assert_eq!(&path, &[0, 2, 1, 3, 4, 5]);
108        assert_eq!(dist, 10.);
109        assert_eq!(graph.dijkstra(1, 1).unwrap(), (0.0, vec![1]));
110    }
111}
algorithms_edu/algo/graph/shortest_path/dijkstra.rs

algorithms_edu/algo/graph/shortest_path/
dijkstra.rs
