haar_lib/graph/
bellman_ford.rs

1//! 負閉路を持つグラフの最短経路 (Bellman-Ford)
2
3use crate::graph::*;
4pub use crate::num::num_inf::NumInf;
5use crate::num::one_zero::Zero;
6use std::{cmp::min, ops::Add};
7
8/// 負閉路を持つグラフの最短経路
9pub fn bellman_ford<D: Direction, E: EdgeTrait>(
10    g: &Graph<D, E>,
11    src: usize,
12) -> Vec<NumInf<E::Weight>>
13where
14    E::Weight: Copy + Ord + Zero + Add<Output = E::Weight>,
15{
16    use self::NumInf::*;
17
18    let n = g.len();
19    let mut ret = vec![Inf; n];
20
21    ret[src] = Value(E::Weight::zero());
22
23    for i in 0..n {
24        for s in 0..n {
25            for e in g.nodes[s].edges.iter() {
26                let (to, cost) = (e.to(), e.weight());
27                if let Value(x) = ret[s] {
28                    match ret[to] {
29                        Value(y) => {
30                            if x + cost < y && i == n - 1 {
31                                ret[to] = NegInf;
32                            } else {
33                                ret[to] = Value(min(y, x + cost));
34                            }
35                        }
36                        Inf => {
37                            ret[to] = Value(x + cost);
38                        }
39                        _ => {}
40                    }
41                }
42            }
43        }
44    }
45
46    for _ in 0..n {
47        for s in 0..n {
48            for e in g.nodes[s].edges.iter() {
49                if ret[s].is_neg_inf() {
50                    ret[e.to()] = NegInf;
51                }
52            }
53        }
54    }
55
56    ret
57}
58
59#[cfg(test)]
60mod tests {
61    use super::{NumInf::*, *};
62
63    #[test]
64    fn test() {
65        let mut g = Graph::<Directed, _>::new(4);
66        g.extend(
67            vec![(0, 1, 2), (0, 2, 3), (1, 2, -5), (1, 3, 1), (2, 3, 2)]
68                .into_iter()
69                .map(|(u, v, w)| Edge::new(u, v, w, ())),
70        );
71        assert_eq!(
72            bellman_ford(&g, 0),
73            [Value(0), Value(2), Value(-3), Value(-1)]
74        );
75
76        let mut g = Graph::<Directed, _>::new(4);
77        g.extend(
78            vec![(0, 1, 2), (0, 2, 3), (1, 2, -5), (1, 3, 1), (2, 3, 2)]
79                .into_iter()
80                .map(|(u, v, w)| Edge::new(u, v, w, ())),
81        );
82        assert_eq!(bellman_ford(&g, 1), [Inf, Value(0), Value(-5), Value(-3)]);
83    }
84}
haar_lib/graph/bellman_ford.rs

haar_lib/graph/
bellman_ford.rs
