Function bellman_ford

pub fn bellman_ford(
    N: usize,
    start: usize,
    edges: &Vec<(usize, usize, i64)>,
) -> (bool, Vec<i64>, Vec<usize>)

ベルマン・フォード法

• 重み付きグラフの単一始点最短路を求める
• 重みが負の場合にも対応
• 各頂点vの距離dist[v]について
  • vに到達不可能な場合 → i64::infinity()
  • vへの最短路が求まる場合 → (vへの最短路長)
  • vへの最短路がいくらでも小さくできる場合 → -i64::infinity()

引数

• N : 頂点数
• start : 始点
• edges : 有向辺 (in, out, weight) の集合

戻り値

• has_negative : (グラフ全体で)負閉路を含むか

• dist : 各頂点への最短路

• prev : 各頂点の最短路について，その頂点の直前に経由した頂点

• 時間計算量: $O(NM)$