reddb_server/storage/engine/pathfinding/
dijkstra_impl.rs

1use super::*;
2
3impl Dijkstra {
4    /// Find shortest weighted path from source to target
5    pub fn shortest_path(graph: &GraphStore, source: &str, target: &str) -> ShortestPathResult {
6        if source == target {
7            return ShortestPathResult {
8                path: Some(Path::start(source)),
9                nodes_visited: 1,
10            };
11        }
12
13        let mut dist: HashMap<String, f64> = HashMap::new();
14        let mut heap: BinaryHeap<DijkstraState> = BinaryHeap::new();
15        let mut nodes_visited = 0;
16
17        dist.insert(source.to_string(), 0.0);
18        heap.push(DijkstraState {
19            node: source.to_string(),
20            cost: 0.0,
21            path: Path::start(source),
22        });
23
24        while let Some(DijkstraState { node, cost, path }) = heap.pop() {
25            nodes_visited += 1;
26
27            // Found target
28            if node == target {
29                return ShortestPathResult {
30                    path: Some(path),
31                    nodes_visited,
32                };
33            }
34
35            // Skip if we've found a better path
36            if let Some(&d) = dist.get(&node) {
37                if cost > d {
38                    continue;
39                }
40            }
41
42            // Explore neighbors
43            for (edge_type, neighbor, weight) in graph.outgoing_edges(&node) {
44                let new_cost = cost + weight as f64;
45
46                if !dist.contains_key(&neighbor) || new_cost < dist[&neighbor] {
47                    dist.insert(neighbor.clone(), new_cost);
48                    heap.push(DijkstraState {
49                        node: neighbor.clone(),
50                        cost: new_cost,
51                        path: path.extend(&neighbor, edge_type, weight as f64),
52                    });
53                }
54            }
55        }
56
57        ShortestPathResult {
58            path: None,
59            nodes_visited,
60        }
61    }
62
63    /// Find shortest paths from source to ALL reachable nodes
64    pub fn shortest_paths_from(graph: &GraphStore, source: &str) -> HashMap<String, Path> {
65        let mut dist: HashMap<String, f64> = HashMap::new();
66        let mut paths: HashMap<String, Path> = HashMap::new();
67        let mut heap: BinaryHeap<DijkstraState> = BinaryHeap::new();
68
69        dist.insert(source.to_string(), 0.0);
70        paths.insert(source.to_string(), Path::start(source));
71        heap.push(DijkstraState {
72            node: source.to_string(),
73            cost: 0.0,
74            path: Path::start(source),
75        });
76
77        while let Some(DijkstraState { node, cost, path }) = heap.pop() {
78            // Skip if we've found a better path
79            if let Some(&d) = dist.get(&node) {
80                if cost > d {
81                    continue;
82                }
83            }
84
85            for (edge_type, neighbor, weight) in graph.outgoing_edges(&node) {
86                let new_cost = cost + weight as f64;
87
88                if !dist.contains_key(&neighbor) || new_cost < dist[&neighbor] {
89                    let new_path = path.extend(&neighbor, edge_type, weight as f64);
90                    dist.insert(neighbor.clone(), new_cost);
91                    paths.insert(neighbor.clone(), new_path.clone());
92                    heap.push(DijkstraState {
93                        node: neighbor.clone(),
94                        cost: new_cost,
95                        path: new_path,
96                    });
97                }
98            }
99        }
100
101        paths
102    }
103}
reddb_server/storage/engine/pathfinding/dijkstra_impl.rs

reddb_server/storage/engine/pathfinding/
dijkstra_impl.rs
