oxicuda_graphalg/shortest_path/
bellman_ford.rs

1//! Bellman-Ford single-source shortest path with negative-cycle detection.
2
3use crate::error::{GraphalgError, GraphalgResult};
4use crate::repr::weighted_graph::WeightedGraph;
5
6#[derive(Debug, Clone)]
7pub struct BellmanFordOutput {
8    pub dist: Vec<f64>,
9    pub parent: Vec<usize>,
10}
11
12pub fn bellman_ford(g: &WeightedGraph, source: usize) -> GraphalgResult<BellmanFordOutput> {
13    if source >= g.n {
14        return Err(GraphalgError::SourceOutOfRange {
15            node: source,
16            n: g.n,
17        });
18    }
19    let mut dist = vec![f64::INFINITY; g.n];
20    let mut parent = vec![usize::MAX; g.n];
21    dist[source] = 0.0;
22    parent[source] = source;
23    let edges = g.all_edges();
24    for _ in 0..g.n.saturating_sub(1) {
25        let mut updated = false;
26        for &(u, v, w) in &edges {
27            if dist[u].is_finite() && dist[u] + w < dist[v] {
28                dist[v] = dist[u] + w;
29                parent[v] = u;
30                updated = true;
31            }
32        }
33        if !updated {
34            break;
35        }
36    }
37    // Negative-cycle check
38    for &(u, v, w) in &edges {
39        if dist[u].is_finite() && dist[u] + w < dist[v] {
40            return Err(GraphalgError::NegativeCycle);
41        }
42    }
43    Ok(BellmanFordOutput { dist, parent })
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn bf_simple_path() {
52        let mut g = WeightedGraph::new(4);
53        g.add_edge(0, 1, 1.0).expect("ok");
54        g.add_edge(1, 2, 2.0).expect("ok");
55        g.add_edge(2, 3, 3.0).expect("ok");
56        let out = bellman_ford(&g, 0).expect("ok");
57        assert!((out.dist[3] - 6.0).abs() < 1e-12);
58    }
59
60    #[test]
61    fn bf_with_negative_edge() {
62        let mut g = WeightedGraph::new(3);
63        g.add_edge(0, 1, 4.0).expect("ok");
64        g.add_edge(0, 2, 5.0).expect("ok");
65        g.add_edge(1, 2, -2.0).expect("ok");
66        let out = bellman_ford(&g, 0).expect("ok");
67        assert!((out.dist[2] - 2.0).abs() < 1e-12);
68    }
69
70    #[test]
71    fn bf_negative_cycle_detected() {
72        let mut g = WeightedGraph::new(3);
73        g.add_edge(0, 1, 1.0).expect("ok");
74        g.add_edge(1, 2, -3.0).expect("ok");
75        g.add_edge(2, 0, 1.0).expect("ok");
76        assert!(matches!(
77            bellman_ford(&g, 0),
78            Err(GraphalgError::NegativeCycle)
79        ));
80    }
81}
oxicuda_graphalg/shortest_path/bellman_ford.rs

oxicuda_graphalg/shortest_path/
bellman_ford.rs
