reddb_server/storage/engine/pathfinding/
bellman_ford_impl.rs

1use super::*;
2
3impl BellmanFord {
4    /// Find shortest path, handling negative weights
5    pub fn shortest_path(graph: &GraphStore, source: &str, target: &str) -> BellmanFordResult {
6        let nodes: Vec<String> = graph.iter_nodes().map(|n| n.id.clone()).collect();
7        let n = nodes.len();
8
9        // Initialize distances
10        let mut dist: HashMap<String, f64> = HashMap::new();
11        let mut predecessor: HashMap<String, (String, String)> = HashMap::new();
12
13        for node in &nodes {
14            dist.insert(node.clone(), f64::INFINITY);
15        }
16        dist.insert(source.to_string(), 0.0);
17
18        let mut nodes_visited = 0;
19
20        // Relax edges V-1 times
21        for _ in 0..n - 1 {
22            let mut changed = false;
23            for node in &nodes {
24                nodes_visited += 1;
25                let d = *dist.get(node).unwrap_or(&f64::INFINITY);
26                if d == f64::INFINITY {
27                    continue;
28                }
29
30                for (edge_type, neighbor, weight) in graph.outgoing_edges(node) {
31                    let new_dist = d + weight as f64;
32                    if new_dist < *dist.get(&neighbor).unwrap_or(&f64::INFINITY) {
33                        dist.insert(neighbor.clone(), new_dist);
34                        predecessor.insert(neighbor.clone(), (node.clone(), edge_type));
35                        changed = true;
36                    }
37                }
38            }
39            if !changed {
40                break; // Early termination if no changes
41            }
42        }
43
44        // Check for negative cycles
45        let mut has_negative_cycle = false;
46        for node in &nodes {
47            let d = *dist.get(node).unwrap_or(&f64::INFINITY);
48            if d == f64::INFINITY {
49                continue;
50            }
51
52            for (_, neighbor, weight) in graph.outgoing_edges(node) {
53                let new_dist = d + weight as f64;
54                if new_dist < *dist.get(&neighbor).unwrap_or(&f64::INFINITY) {
55                    has_negative_cycle = true;
56                    break;
57                }
58            }
59            if has_negative_cycle {
60                break;
61            }
62        }
63
64        // Reconstruct path to target
65        let path = if has_negative_cycle {
66            None
67        } else if dist.get(target).map(|d| d.is_finite()).unwrap_or(false) {
68            let mut path_nodes = vec![target.to_string()];
69            let mut path_edges = Vec::new();
70            let mut current = target.to_string();
71
72            while let Some((pred, edge_type)) = predecessor.get(&current) {
73                path_nodes.push(pred.clone());
74                path_edges.push(edge_type.clone());
75                current = pred.clone();
76                if current == source {
77                    break;
78                }
79            }
80
81            path_nodes.reverse();
82            path_edges.reverse();
83
84            Some(Path {
85                nodes: path_nodes,
86                total_weight: *dist.get(target).unwrap_or(&0.0),
87                edge_types: path_edges,
88            })
89        } else {
90            None
91        };
92
93        BellmanFordResult {
94            path,
95            distances: dist,
96            has_negative_cycle,
97            nodes_visited,
98        }
99    }
100}
reddb_server/storage/engine/pathfinding/bellman_ford_impl.rs

reddb_server/storage/engine/pathfinding/
bellman_ford_impl.rs
