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

ベルマン・フォード法

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

引数

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

戻り値

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

  • dist : 各頂点への最短路

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

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