haar_lib/graph/
warshall_floyd.rs

1//! 全頂点間最短経路長
2//!
3//! # Problems
4//! - <https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C>
5//! - <https://atcoder.jp/contests/abc375/tasks/abc375_f>
6
7#![allow(clippy::needless_range_loop)]
8
9use crate::graph::*;
10use crate::num::one_zero::Zero;
11use std::ops::Add;
12
13enum Result<T> {
14    NegativeLoop,
15    Valid(Vec<Vec<Option<T>>>),
16}
17
18/// グラフの全頂点間の最短距離を管理する。
19pub struct WarshallFloyd<T> {
20    len: usize,
21    result: Result<T>,
22}
23
24impl<T> WarshallFloyd<T>
25where
26    T: Copy + Ord + Add<Output = T> + Zero,
27{
28    /// `WarshallFloyd<T>`を生成する。
29    ///
30    /// **Time complexity** $O(n^3)$
31    pub fn new<D: Direction, E: EdgeTrait<Weight = T>>(g: &Graph<D, E>) -> Self {
32        let zero = E::Weight::zero();
33        let n = g.len();
34        let mut dist = vec![vec![None; n]; n];
35
36        for i in 0..n {
37            dist[i][i] = Some(zero);
38        }
39        for e in g.nodes_iter().flat_map(|v: &GraphNode<E>| &v.edges) {
40            dist[e.from()][e.to()] = Some(e.weight());
41        }
42
43        for k in 0..n {
44            for i in 0..n {
45                for j in 0..n {
46                    if let (Some(a), Some(b)) = (dist[i][k], dist[k][j]) {
47                        let s = a + b;
48                        dist[i][j] = dist[i][j].map(|x| x.min(s)).or(Some(s));
49                    }
50                }
51            }
52        }
53
54        for i in 0..n {
55            if dist[i][i].unwrap() < zero {
56                return Self {
57                    len: n,
58                    result: Result::NegativeLoop,
59                };
60            }
61        }
62
63        Self {
64            len: n,
65            result: Result::Valid(dist),
66        }
67    }
68
69    /// `from`から`to`への最短距離を返す。
70    pub fn dist(&self, from: usize, to: usize) -> Option<T> {
71        match &self.result {
72            Result::NegativeLoop => panic!(),
73            Result::Valid(dist) => dist[from][to],
74        }
75    }
76
77    /// 内部で保持している距離テーブルへの参照を返す。
78    pub fn table(&self) -> Option<&Vec<Vec<Option<T>>>> {
79        match &self.result {
80            Result::NegativeLoop => None,
81            Result::Valid(dist) => Some(dist),
82        }
83    }
84
85    /// 負の閉路があれば`true`を返す。
86    ///
87    /// **Time complexity** $O(1)$
88    pub fn has_negative_loop(&self) -> bool {
89        matches!(self.result, Result::NegativeLoop)
90    }
91
92    /// 有向辺を追加して、最短距離を再計算する。
93    ///
94    /// **Time complexity** $O(n^2)$
95    pub fn add_edge(&mut self, from: usize, to: usize, d: T) {
96        match &mut self.result {
97            Result::NegativeLoop => {}
98            Result::Valid(dist) => {
99                for i in 0..self.len {
100                    for j in 0..self.len {
101                        if let (Some(a), Some(b)) = (dist[i][from], dist[to][j]) {
102                            let s = a + b + d;
103                            dist[i][j] = dist[i][j].map(|x| x.min(s)).or(Some(s));
104                        }
105                    }
106                }
107            }
108        }
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115
116    #[test]
117    fn test() {
118        // https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C
119        let mut g = Graph::<Directed, _>::new(4);
120        g.extend(
121            vec![
122                (0, 1, 1),
123                (0, 2, 5),
124                (1, 2, 2),
125                (1, 3, 4),
126                (2, 3, 1),
127                (3, 2, 7),
128            ]
129            .into_iter()
130            .map(|(u, v, w)| Edge::new(u, v, w, ())),
131        );
132
133        assert_eq!(
134            WarshallFloyd::new(&g).table(),
135            Some(&vec![
136                vec![Some(0), Some(1), Some(3), Some(4)],
137                vec![None, Some(0), Some(2), Some(3)],
138                vec![None, None, Some(0), Some(1)],
139                vec![None, None, Some(7), Some(0)]
140            ])
141        );
142
143        let mut g = Graph::<Directed, _>::new(4);
144        g.extend(
145            vec![
146                (0, 1, 1),
147                (0, 2, -5),
148                (1, 2, 2),
149                (1, 3, 4),
150                (2, 3, 1),
151                (3, 2, 7),
152            ]
153            .into_iter()
154            .map(|(u, v, w)| Edge::new(u, v, w, ())),
155        );
156
157        assert_eq!(
158            WarshallFloyd::new(&g).table(),
159            Some(&vec![
160                vec![Some(0), Some(1), Some(-5), Some(-4)],
161                vec![None, Some(0), Some(2), Some(3)],
162                vec![None, None, Some(0), Some(1)],
163                vec![None, None, Some(7), Some(0)]
164            ])
165        );
166
167        let mut g = Graph::<Directed, _>::new(4);
168        g.extend(
169            vec![
170                (0, 1, 1),
171                (0, 2, 5),
172                (1, 2, 2),
173                (1, 3, 4),
174                (2, 3, 1),
175                (3, 2, -7),
176            ]
177            .into_iter()
178            .map(|(u, v, w)| Edge::new(u, v, w, ())),
179        );
180
181        assert!(WarshallFloyd::new(&g).has_negative_loop());
182    }
183}
haar_lib/graph/warshall_floyd.rs

haar_lib/graph/
warshall_floyd.rs
