oxicuda_graphalg/shortest_path/
johnson.rs

1//! Johnson's algorithm: all-pairs shortest path via reweighting (Bellman-Ford then Dijkstra).
2
3use crate::error::{GraphalgError, GraphalgResult};
4use crate::repr::weighted_graph::WeightedGraph;
5
6use super::bellman_ford::bellman_ford;
7use super::dijkstra::dijkstra;
8
9/// Returns row-major n x n distance matrix using Johnson's reweighting trick.
10pub fn johnson(g: &WeightedGraph) -> GraphalgResult<Vec<f64>> {
11    let n = g.n;
12    // Augment graph with extra source (index n) connected with weight 0 to all nodes.
13    let mut aug = WeightedGraph::new(n + 1);
14    for (u, adj) in g.edges.iter().enumerate() {
15        for &(v, w) in adj {
16            aug.add_edge(u, v, w)?;
17        }
18    }
19    for v in 0..n {
20        aug.add_edge(n, v, 0.0)?;
21    }
22    let h_out = bellman_ford(&aug, n)?;
23    let h = h_out.dist;
24    // Reweight: w'(u,v) = w(u,v) + h[u] - h[v]
25    let mut reweighted = WeightedGraph::new(n);
26    for (u, adj) in g.edges.iter().enumerate() {
27        for &(v, w) in adj {
28            let nw = w + h[u] - h[v];
29            if nw < 0.0 {
30                return Err(GraphalgError::NumericalInstability(
31                    "reweighting produced negative edge".to_string(),
32                ));
33            }
34            reweighted.add_edge(u, v, nw)?;
35        }
36    }
37    let mut dist = vec![f64::INFINITY; n * n];
38    for s in 0..n {
39        let out = dijkstra(&reweighted, s)?;
40        for t in 0..n {
41            if out.dist[t].is_finite() {
42                dist[s * n + t] = out.dist[t] - h[s] + h[t];
43            }
44        }
45    }
46    Ok(dist)
47}
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn johnson_matches_fw() {
55        // Use only positive edges so it matches Floyd-Warshall easily.
56        let mut g = WeightedGraph::new(3);
57        g.add_edge(0, 1, 1.0).expect("ok");
58        g.add_edge(1, 2, 2.0).expect("ok");
59        g.add_edge(0, 2, 5.0).expect("ok");
60        let d = johnson(&g).expect("ok");
61        assert!((d[0 * 3 + 2] - 3.0).abs() < 1e-9);
62    }
63}
oxicuda_graphalg/shortest_path/johnson.rs

oxicuda_graphalg/shortest_path/
johnson.rs
