graph_shortest_path/
bellman_ford.rs

1use graph_core::{Graph, GraphError, NodeId};
2use std::collections::HashMap;
3
4/// Result of a Bellman-Ford shortest-path search.
5pub struct BellmanFordResult {
6    /// Map from `NodeId` to the shortest distance from the source.
7    ///
8    /// Nodes not reachable from the source are absent.
9    pub distances: HashMap<NodeId, f64>,
10    /// Parent of each node in the shortest-path tree.
11    pub parents: HashMap<NodeId, NodeId>,
12}
13
14/// Runs the Bellman-Ford algorithm from `source`.
15///
16/// Unlike Dijkstra, Bellman-Ford handles **negative edge weights**. It detects
17/// negative-weight cycles reachable from `source` and returns an error if one
18/// exists.
19///
20/// # Algorithm
21///
22/// Relax all edges V-1 times. On the V-th relaxation pass, if any distance
23/// can still be improved a negative-weight cycle exists.
24///
25/// # Errors
26///
27/// - [`GraphError::NodeNotFound`] if `source` is not in the graph.
28/// - [`GraphError::NegativeCycle`] if a negative-weight cycle is reachable.
29///
30/// # Complexity
31///
32/// O(V · E).
33///
34/// # Examples
35///
36/// ```
37/// use graph_core::{AdjacencyList, Graph};
38/// use graph_shortest_path::bellman_ford;
39///
40/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
41/// let a = g.add_node(());
42/// let b = g.add_node(());
43/// let c = g.add_node(());
44/// g.add_edge(a, b, 4.0).unwrap();
45/// g.add_edge(a, c, 2.0).unwrap();
46/// g.add_edge(c, b, -1.0).unwrap(); // negative weight, but no negative cycle
47///
48/// let result = bellman_ford(&g, a).unwrap();
49/// assert_eq!(result.distances[&b], 1.0); // a→c→b: 2 + (-1) = 1
50/// ```
51pub fn bellman_ford<G>(graph: &G, source: NodeId) -> Result<BellmanFordResult, GraphError>
52where
53    G: Graph<Weight = f64>,
54{
55    if !graph.contains_node(source) {
56        return Err(GraphError::NodeNotFound(source));
57    }
58
59    // Initialise: source = 0, all others = ∞.
60    let mut distances: HashMap<NodeId, f64> = graph
61        .nodes()
62        .map(|n| (n, if n == source { 0.0 } else { f64::INFINITY }))
63        .collect();
64    let mut parents: HashMap<NodeId, NodeId> = HashMap::new();
65
66    let v = graph.node_count();
67
68    // Collect all edges once to avoid repeated iteration over the graph.
69    let edges = graph.all_edges();
70
71    // Relax V-1 times.
72    for _ in 0..v.saturating_sub(1) {
73        let mut updated = false;
74        for edge in &edges {
75            let u_dist = distances[&edge.source];
76            if u_dist == f64::INFINITY {
77                continue;
78            }
79            let candidate = u_dist + edge.weight;
80            if candidate < distances[&edge.target] {
81                distances.insert(edge.target, candidate);
82                parents.insert(edge.target, edge.source);
83                updated = true;
84            }
85        }
86        // Early termination: if no update occurred, we're done.
87        if !updated {
88            break;
89        }
90    }
91
92    // V-th pass: if any relaxation still succeeds, there's a negative cycle.
93    for edge in &edges {
94        let u_dist = distances[&edge.source];
95        if u_dist == f64::INFINITY {
96            continue;
97        }
98        if u_dist + edge.weight < distances[&edge.target] {
99            return Err(GraphError::NegativeCycle);
100        }
101    }
102
103    // Remove unreachable nodes (distance still ∞) from the result map.
104    distances.retain(|_, d| d.is_finite());
105
106    Ok(BellmanFordResult { distances, parents })
107}
graph_shortest_path/bellman_ford.rs

graph_shortest_path/
bellman_ford.rs
