flex_algo/
dijkstra.rs

1use std::{collections::HashSet, vec};
2use std::fmt::Debug;
3use crate::priority_queue::PriorityQueue;
4
5/// Dijkstra algorithm
6///
7/// This crate implements a Dijkstra algorithm to compute the shortest path by given graph.
8/// 
9#[derive(Debug)]
10pub struct Dijkstra {
11    adjacent_list: Vec<Vec<(usize, usize)>>,
12    num_nodes: usize,
13}
14
15impl Dijkstra {
16    /// Create a new Dijkstra graph with edges tuple(current, neighbor, weight) Vec
17    /// 
18    /// # Example
19    /// 
20    /// ```
21    /// use flex_algo::Dijkstra;
22    /// 
23    /// let times = vec![(0, 1, 9), (0, 3, 2), (1, 4, 1), (3, 1, 4), (3, 4, 6), (2, 1, 3), (4, 2, 7), (2, 0, 5)];
24    /// let dijkstra = Dijkstra::new(5, times);
25    /// 
26    /// ```
27    pub fn new(num_nodes: usize, edges: Vec<(usize, usize, usize)>) -> Self {
28        let mut adjacent_list = vec![Vec::new(); num_nodes];
29        for edge in edges {
30            let source = edge.0;
31            let target = edge.1;
32            adjacent_list[source].push((target, edge.2));
33        }
34        Dijkstra {
35            adjacent_list,
36            num_nodes,
37        }
38    }
39
40    /// Return the shortest path
41    /// 
42    /// # Example
43    /// 
44    /// ```
45    /// use flex_algo::Dijkstra;
46    /// 
47    /// let times = vec![(0, 1, 9), (0, 3, 2), (1, 4, 1), (3, 1, 4), (3, 4, 6), (2, 1, 3), (4, 2, 7), (2, 0, 5)];
48    /// let dijkstra = Dijkstra::new(5, times);
49    /// let (max, path) =  dijkstra.shortest_path(0).unwrap();
50    /// println!("shortest path: {:?}", path);
51    /// assert_eq!(max, 14);
52    /// 
53    /// ```
54    pub fn shortest_path(&self, node: usize) -> Option<(usize, Vec<usize>)> {
55        let mut distances = vec![usize::MAX; self.num_nodes];
56        distances[node] = 0;
57        let distances_ptr = distances.as_mut_ptr();
58        let mut heap = PriorityQueue::new(|a: &usize,b:&usize| distances.get(*a).cloned() < distances.get(*b).cloned());
59        let mut seens = HashSet::new();
60        let mut visit = Vec::new();
61        heap.push(node);
62
63        while !heap.is_empty() {
64            let vertex = heap.pop().unwrap();
65            if !seens.contains(&vertex) {
66                visit.push(vertex);
67                seens.insert(vertex);
68                let adjacent = &self.adjacent_list[vertex];
69                for pair in adjacent {
70                    let neighbor_vertex = pair.0;
71                    let weight = pair.1;
72                    if distances[vertex] + weight < distances[neighbor_vertex] {
73                        unsafe {
74                            *distances_ptr.add(neighbor_vertex) = distances[vertex] + weight;
75                        }
76                        heap.push(neighbor_vertex);
77                    }
78                }
79            }
80        }
81        distances.sort();
82        let max = distances.pop().unwrap();
83        if max < usize::MAX {
84            return Some((max, visit));
85        }
86        None
87    }
88}
89
90#[cfg(test)]
91mod tests {
92
93    use super::*;
94
95    #[test]
96    fn test_dijkstra() {
97        let times = vec![
98          (0, 1, 9), (0, 3, 2), (1, 4, 1), (3, 1, 4), (3, 4, 6), (2, 1, 3), (4, 2, 7), (2, 0, 5)
99        ];
100        let dijkstra = Dijkstra::new(5, times);
101        println!("Dijkstra: {:?}", dijkstra);
102        // panic!()
103    }
104
105    #[test]
106    fn test_shortest_path() {
107        let times = vec![
108          (0, 1, 9), (0, 3, 2), (1, 4, 1), (3, 1, 4), (3, 4, 6), (2, 1, 3), (4, 2, 7), (2, 0, 5)
109        ];
110        let dijkstra = Dijkstra::new(5, times);
111        let (max, path) =  dijkstra.shortest_path(0).unwrap();
112        println!("shortest path: {:?}", path);
113        assert_eq!(max, 14);
114        // panic!();
115    }
116}
flex_algo/dijkstra.rs

flex_algo/
dijkstra.rs
