uni_algo/algo/algorithms/
bellman_ford.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Bellman-Ford Algorithm.
5//!
6//! Computes shortest paths from a source node to all other nodes in a weighted graph.
7//! Unlike Dijkstra, it handles negative edge weights.
8//! Detects negative cycles.
9
10use crate::algo::GraphProjection;
11use crate::algo::algorithms::Algorithm;
12use uni_common::core::id::Vid;
13
14pub struct BellmanFord;
15
16#[derive(Debug, Clone)]
17pub struct BellmanFordConfig {
18    pub source: Vid,
19}
20
21impl Default for BellmanFordConfig {
22    fn default() -> Self {
23        Self {
24            source: Vid::from(0),
25        }
26    }
27}
28
29pub struct BellmanFordResult {
30    pub distances: Vec<(Vid, f64)>,
31    pub has_negative_cycle: bool,
32}
33
34impl Algorithm for BellmanFord {
35    type Config = BellmanFordConfig;
36    type Result = BellmanFordResult;
37
38    fn name() -> &'static str {
39        "bellman_ford"
40    }
41
42    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
43        let source_slot = match graph.to_slot(config.source) {
44            Some(slot) => slot,
45            None => {
46                return BellmanFordResult {
47                    distances: Vec::new(),
48                    has_negative_cycle: false,
49                };
50            }
51        };
52
53        let n = graph.vertex_count();
54        let mut dist = vec![f64::INFINITY; n];
55        dist[source_slot as usize] = 0.0;
56
57        // Relax V-1 times
58        for _ in 0..n - 1 {
59            let mut changed = false;
60            for u in 0..n {
61                if dist[u] == f64::INFINITY {
62                    continue;
63                }
64
65                // Iterate over edges (u, v)
66                for (i, &v_slot) in graph.out_neighbors(u as u32).iter().enumerate() {
67                    let v = v_slot as usize;
68                    let weight = if graph.has_weights() {
69                        graph.out_weight(u as u32, i)
70                    } else {
71                        1.0
72                    };
73
74                    if dist[u] + weight < dist[v] {
75                        dist[v] = dist[u] + weight;
76                        changed = true;
77                    }
78                }
79            }
80            if !changed {
81                break;
82            }
83        }
84
85        // Check for negative cycles
86        let mut has_negative_cycle = false;
87        for u in 0..n {
88            if dist[u] == f64::INFINITY {
89                continue;
90            }
91            for (i, &v_slot) in graph.out_neighbors(u as u32).iter().enumerate() {
92                let v = v_slot as usize;
93                let weight = if graph.has_weights() {
94                    graph.out_weight(u as u32, i)
95                } else {
96                    1.0
97                };
98
99                if dist[u] + weight < dist[v] {
100                    has_negative_cycle = true;
101                    break;
102                }
103            }
104            if has_negative_cycle {
105                break;
106            }
107        }
108
109        if has_negative_cycle {
110            BellmanFordResult {
111                distances: Vec::new(),
112                has_negative_cycle: true,
113            }
114        } else {
115            let results = dist
116                .into_iter()
117                .enumerate()
118                .filter(|(_, d)| *d < f64::INFINITY)
119                .map(|(slot, d)| (graph.to_vid(slot as u32), d))
120                .collect();
121
122            BellmanFordResult {
123                distances: results,
124                has_negative_cycle: false,
125            }
126        }
127    }
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crate::algo::test_utils::build_test_graph;
134
135    #[test]
136    fn test_bellman_ford_simple() {
137        // 0 -> 1 (1.0), 1 -> 2 (1.0)
138        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
139        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
140        let graph = build_test_graph(vids, edges); // weight 1.0
141
142        let config = BellmanFordConfig {
143            source: Vid::from(0),
144        };
145        let result = BellmanFord::run(&graph, config);
146
147        assert!(!result.has_negative_cycle);
148        let dists: std::collections::HashMap<_, _> = result.distances.into_iter().collect();
149        assert_eq!(dists[&Vid::from(0)], 0.0);
150        assert_eq!(dists[&Vid::from(1)], 1.0);
151        assert_eq!(dists[&Vid::from(2)], 2.0);
152    }
153
154    // Note: build_test_graph doesn't support custom weights yet.
155    // We would need a custom builder test utility to test negative cycles properly.
156    // For now, testing logic structure with default weights.
157}
uni_algo/algo/algorithms/bellman_ford.rs

uni_algo/algo/algorithms/
bellman_ford.rs
