Bellman Ford法
(graph/bellman-ford.hpp)

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "graph/bellman-ford.hpp"

説明

• ベルマンフォード法
• 負のコストを含めた最短経路を求める

• O(NM)

• Constructor

  BellmanFord<T, const T&(*op)(const T&, const T&)>(const Graph<T> &r);
  

• 頂点sを始点として最短経路を求める

  void solve(int s)
  

• i までの最短距離を変数名[i]で取得
• 負閉路の場合はinfが出力される

  const T &operator[](const int i)
  

• 負閉路判定

  bool is_cycle(const int i)
  

Depends on

• Graph Template (graph/template.hpp)

Verified with

• test/aoj/GRL/GRL_1_B.test.cpp

Code

#include "template.hpp"

template <class T, const T&(*op)(const T&, const T&)>
struct BellmanFord {
  BellmanFord(const Graph<T> &r): root(r), n(r.size()){
    inf = -op(inf, -inf);
    res.assign(n, inf);
  }
  void solve(const int s){
    assert(0 <= s && s < n);
    res[s] = 0;
    for(int i = 1; i < n; i++) for(int j = 0; j < n; j++){
      if(res[j] != inf) for(const auto &x : root[j]){
        res[x] = op(res[x], res[j] + x.cost);
      }
    }
    vector<int> loop(n);
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
      if(res[j] != inf) for(const auto &x : root[j]){
        if(op(res[x] + op(1,-1), res[j] + x.cost) == res[j] + x.cost){
          res[x] = res[j] + x.cost;
          loop[x] = 1;
        }
        if(loop[j]) loop[x] = 1;
      }
    }
    for(int i = 0; i < n; i++) if(loop[i]) res[i] = -inf;
  }
  const T &operator[](const int i) const{
    assert(0 <= i && i < n);
    return res[i];
  }
  bool is_cycle(const int i) const{
    assert(0 <= i && i < n);
    return res[i] == -inf;
  }
  private:
  const Graph<T> &root;
  vector<T> res;
  int n;
  T inf = numeric_limits<T>::max()-1;
};

#line 2 "graph/template.hpp"

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;
#line 2 "graph/bellman-ford.hpp"

template <class T, const T&(*op)(const T&, const T&)>
struct BellmanFord {
  BellmanFord(const Graph<T> &r): root(r), n(r.size()){
    inf = -op(inf, -inf);
    res.assign(n, inf);
  }
  void solve(const int s){
    assert(0 <= s && s < n);
    res[s] = 0;
    for(int i = 1; i < n; i++) for(int j = 0; j < n; j++){
      if(res[j] != inf) for(const auto &x : root[j]){
        res[x] = op(res[x], res[j] + x.cost);
      }
    }
    vector<int> loop(n);
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
      if(res[j] != inf) for(const auto &x : root[j]){
        if(op(res[x] + op(1,-1), res[j] + x.cost) == res[j] + x.cost){
          res[x] = res[j] + x.cost;
          loop[x] = 1;
        }
        if(loop[j]) loop[x] = 1;
      }
    }
    for(int i = 0; i < n; i++) if(loop[i]) res[i] = -inf;
  }
  const T &operator[](const int i) const{
    assert(0 <= i && i < n);
    return res[i];
  }
  bool is_cycle(const int i) const{
    assert(0 <= i && i < n);
    return res[i] == -inf;
  }
  private:
  const Graph<T> &root;
  vector<T> res;
  int n;
  T inf = numeric_limits<T>::max()-1;
};

Back to top page