icentral_graph/
find_single_source_shortest_paths.rs

1crate::ix!();
2
3impl<GH> FindSingleSourceShortestPaths for Graph<GH> {
4
5    fn find_single_source_shortest_paths(&self, s: NodeId) 
6    -> Result<DistanceMap,BetweennessCentralityError> 
7    {
8        let distances_name = name!(self.name(), format!("sssp_distances_for_{}", s));
9
10        let mut distances = DistanceMap::new(
11            self.num_nodes(), 
12            distances_name
13        );
14
15        let queue_name = name![
16            self.name(), 
17            format!("find_single_source_shortest_paths_for_{}::queue", s)
18        ];
19
20        let mut queue = NodeIdQueue::empty(queue_name);
21
22        queue.enqueue(s);
23
24        distances.set_zero_distance(s);
25
26        while let Some(v) = queue.dequeue() {
27
28            let nbr_vec = self.neighbors(v);
29
30            for &nbr in nbr_vec.iter() {
31
32                if distances.is_infinite(nbr) {
33
34                    distances.set_one_step_away(nbr, v);
35
36                    queue.enqueue(nbr);
37                }
38            }
39        }
40
41        Ok(distances)
42    }
43}