cp_library_rs/graph/
bellman_ford.rs

1//! ベルマン・フォード法
2
3use crate::utils::consts::Infinity;
4
5/// ベルマン・フォード法
6/// - 重み付きグラフの単一始点最短路を求める
7/// - 重みが負の場合にも対応
8/// - 各頂点`v`の距離`dist[v]`について
9///   - vに到達不可能な場合     → [`i64::infinity()`]
10///   - vへの最短路が求まる場合 → `(vへの最短路長)`
11///   - vへの最短路がいくらでも小さくできる場合 → `-i64::infinity()`
12///
13/// 引数
14/// - `N` : 頂点数
15/// - `start` : 始点
16/// - `edges` : 有向辺 `(in, out, weight)` の集合
17///
18/// 戻り値
19/// - `has_negative` : (グラフ全体で)負閉路を含むか
20/// - `dist` : 各頂点への最短路
21/// - `prev` : 各頂点の最短路について，その頂点の直前に経由した頂点
22///
23/// - 時間計算量: $`O(NM)`$
24pub fn bellman_ford(
25    N: usize,
26    start: usize,
27    edges: &Vec<(usize, usize, i64)>,
28) -> (bool, Vec<i64>, Vec<usize>) {
29    let mut dist = vec![2 * i64::infinity(); N];
30    dist[start] = 0;
31    let mut prev = vec![usize::infinity(); N];
32
33    for _ in 0..N {
34        for &(u, v, w) in edges {
35            // 緩和
36            if dist[v] > dist[u] + w {
37                dist[v] = dist[u] + w;
38                prev[v] = u;
39            }
40        }
41    }
42
43    // 負閉路検出
44    let mut has_negative = false;
45
46    for &(u, v, w) in edges {
47        if dist[v] > dist[u] + w {
48            has_negative = true;
49            // 始点から到達できる場合
50            if dist[u] < i64::infinity() {
51                dist[v] = -i64::infinity();
52            }
53        }
54    }
55
56    // 到達できない頂点をINFに
57    dist.iter_mut().for_each(|d| {
58        if *d > i64::infinity() {
59            *d = i64::infinity();
60        }
61    });
62
63    // 影響範囲を調べる（もう一度ベルマンフォード）
64    for _ in 0..N {
65        for &(u, v, w) in edges {
66            if dist[u] == i64::infinity() || dist[v] == i64::infinity() {
67                continue;
68            }
69            // 緩和
70            if dist[v] > dist[u] + w {
71                dist[v] = -i64::infinity();
72            }
73        }
74    }
75
76    (has_negative, dist, prev)
77}
cp_library_rs/graph/bellman_ford.rs

cp_library_rs/graph/
bellman_ford.rs
