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