ベルマンフォード bellman ford クラス実装 負閉路 サイクル検出 ループ検出

ベルマンフォード 最短経路 ライブラリ

ベルマンフォードとは？

  • 単一始点最短距離を求める
  • 辺の重みが負でもいい
  • その代わりにダイクストラより遅い。O(VE)
  • 負閉路が検出できる

具体例

その他

  • 競プロでの問題では必要となる時が少ないのか、bellman fordの実装は初めて
  • 負のコストがあるのでダイクストラではダメ
  • 頂点の数をVとして、V-1回まわすことで伝播するというのは他でも使えるかもしれない
  • 必ず止まるという安心感もある
  • 全く詰まらず実装できて成長を感じる

2021年ver

struct Edge{
  ll to;
  ll cost;
  Edge(ll to, ll cost): to(to), cost(cost) {}
  Edge(){
    to = 0;
    cost = 0;
  }
};

struct BellmanFord{
  vector<vector<Edge> > edges;
  vector<ll> dist;
  bool has_negative_cycle;
  
  BellmanFord(ll sz){
    edges.resize(sz);
    dist.resize(sz, inf);
    has_negative_cycle=false;
  }

  // 単方向。cは負も可能
  void add_edge(ll a, ll b, ll c){
    edges[a].push_back(Edge(b, c));
  }

  // 計算量 V * E
  vector<ll> calc_shortest_path(ll start){
    dist[start] = 0;
    ll N = dist.size();
    ll loop = N - 1;
    while(loop--){
      rep(i, N){
        if(dist[i]==inf) continue;
        for(auto edge : edges[i]){
          chmin(dist[edge.to], dist[i] + edge.cost);
        }
      }
    }
    
    // 負閉路がないならここで収束している
    // もう1回回して変化があれば負閉路あり
    auto temp = dist;
    rep(i, N){
      if(dist[i]==inf) continue;
      for(auto edge : edges[i]){
        if(chmin(dist[edge.to], dist[i] + edge.cost)){
          has_negative_cycle=true;
        }
      }
    }
    return dist;
  }
};