oxihuman_core/
bellman_ford.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Bellman-Ford single-source shortest paths on a weighted directed graph.
6
7/// A weighted directed edge.
8#[derive(Debug, Clone, Copy)]
9pub struct BfEdge {
10    pub from: usize,
11    pub to: usize,
12    pub weight: f32,
13}
14
15/// A weighted directed graph for Bellman-Ford.
16pub struct BfGraph {
17    pub n: usize,
18    pub edges: Vec<BfEdge>,
19}
20
21impl BfGraph {
22    pub fn new(n: usize) -> Self {
23        BfGraph {
24            n,
25            edges: Vec::new(),
26        }
27    }
28}
29
30/// Create a new Bellman-Ford graph with `n` vertices.
31pub fn new_bf_graph(n: usize) -> BfGraph {
32    BfGraph::new(n)
33}
34
35/// Add a directed weighted edge.
36pub fn bf_add_edge(g: &mut BfGraph, from: usize, to: usize, weight: f32) {
37    g.edges.push(BfEdge { from, to, weight });
38}
39
40/// Result of Bellman-Ford.
41pub struct BfResult {
42    /// Shortest distances from source; `f32::INFINITY` if unreachable.
43    pub dist: Vec<f32>,
44    /// `true` if a negative-weight cycle is reachable from `src`.
45    pub has_negative_cycle: bool,
46}
47
48/// Run Bellman-Ford from `src`. Returns `BfResult`.
49pub fn bellman_ford(g: &BfGraph, src: usize) -> BfResult {
50    let n = g.n;
51    let mut dist = vec![f32::INFINITY; n];
52    if src < n {
53        dist[src] = 0.0;
54    }
55
56    /* relax edges n-1 times */
57    for _ in 0..n.saturating_sub(1) {
58        for e in &g.edges {
59            if dist[e.from].is_finite() && dist[e.from] + e.weight < dist[e.to] {
60                dist[e.to] = dist[e.from] + e.weight;
61            }
62        }
63    }
64
65    /* check for negative cycles */
66    let mut has_negative_cycle = false;
67    for e in &g.edges {
68        if dist[e.from].is_finite() && dist[e.from] + e.weight < dist[e.to] {
69            has_negative_cycle = true;
70            break;
71        }
72    }
73
74    BfResult {
75        dist,
76        has_negative_cycle,
77    }
78}
79
80/// Return the shortest distance from `src` to `dst`, or `None` if unreachable.
81pub fn bf_distance(g: &BfGraph, src: usize, dst: usize) -> Option<f32> {
82    if dst >= g.n {
83        return None;
84    }
85    let r = bellman_ford(g, src);
86    if r.dist[dst].is_finite() {
87        Some(r.dist[dst])
88    } else {
89        None
90    }
91}
92
93/// Return `true` if the graph has a negative cycle reachable from `src`.
94pub fn bf_has_negative_cycle(g: &BfGraph, src: usize) -> bool {
95    bellman_ford(g, src).has_negative_cycle
96}
97
98/// Return number of edges in the graph.
99pub fn bf_edge_count(g: &BfGraph) -> usize {
100    g.edges.len()
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn test_simple_positive_weights() {
109        /* 0 -1-> 1 -2-> 2 */
110        let mut g = new_bf_graph(3);
111        bf_add_edge(&mut g, 0, 1, 1.0);
112        bf_add_edge(&mut g, 1, 2, 2.0);
113        let d = bf_distance(&g, 0, 2).expect("should succeed");
114        assert!((d - 3.0).abs() < 1e-6);
115    }
116
117    #[test]
118    fn test_negative_edge_no_cycle() {
119        /* 0 -5-> 1; 0 -2-> 2; 2 -(-3)-> 1 */
120        let mut g = new_bf_graph(3);
121        bf_add_edge(&mut g, 0, 1, 5.0);
122        bf_add_edge(&mut g, 0, 2, 2.0);
123        bf_add_edge(&mut g, 2, 1, -3.0);
124        let d = bf_distance(&g, 0, 1).expect("should succeed");
125        assert!((d - (-1.0)).abs() < 1e-6); /* 2 + (-3) = -1 */
126    }
127
128    #[test]
129    fn test_negative_cycle_detected() {
130        let mut g = new_bf_graph(3);
131        bf_add_edge(&mut g, 0, 1, 1.0);
132        bf_add_edge(&mut g, 1, 2, -5.0);
133        bf_add_edge(&mut g, 2, 0, 1.0); /* cycle weight -3 */
134        assert!(bf_has_negative_cycle(&g, 0));
135    }
136
137    #[test]
138    fn test_unreachable_node() {
139        let mut g = new_bf_graph(4);
140        bf_add_edge(&mut g, 0, 1, 1.0);
141        /* node 2, 3 disconnected */
142        assert!(bf_distance(&g, 0, 3).is_none());
143    }
144
145    #[test]
146    fn test_src_to_itself() {
147        let g = new_bf_graph(3);
148        assert_eq!(bf_distance(&g, 1, 1), Some(0.0));
149    }
150
151    #[test]
152    fn test_edge_count() {
153        let mut g = new_bf_graph(3);
154        bf_add_edge(&mut g, 0, 1, 1.0);
155        bf_add_edge(&mut g, 1, 2, 2.0);
156        assert_eq!(bf_edge_count(&g), 2);
157    }
158
159    #[test]
160    fn test_no_negative_cycle() {
161        let mut g = new_bf_graph(3);
162        bf_add_edge(&mut g, 0, 1, 3.0);
163        bf_add_edge(&mut g, 1, 2, 3.0);
164        assert!(!bf_has_negative_cycle(&g, 0));
165    }
166
167    #[test]
168    fn test_parallel_edges_take_minimum() {
169        let mut g = new_bf_graph(2);
170        bf_add_edge(&mut g, 0, 1, 10.0);
171        bf_add_edge(&mut g, 0, 1, 3.0);
172        let d = bf_distance(&g, 0, 1).expect("should succeed");
173        assert!((d - 3.0).abs() < 1e-6);
174    }
175
176    #[test]
177    fn test_all_distances() {
178        let mut g = new_bf_graph(4);
179        bf_add_edge(&mut g, 0, 1, 1.0);
180        bf_add_edge(&mut g, 0, 2, 4.0);
181        bf_add_edge(&mut g, 1, 2, 2.0);
182        bf_add_edge(&mut g, 1, 3, 6.0);
183        bf_add_edge(&mut g, 2, 3, 1.0);
184        let r = bellman_ford(&g, 0);
185        assert!((r.dist[3] - 4.0).abs() < 1e-6); /* 0->1->2->3 = 4 */
186    }
187}
oxihuman_core/bellman_ford.rs

oxihuman_core/
bellman_ford.rs
