bellman-ford.cpp

std::vector<int> bellman_ford(const Graph& g,int s){
  std::vector<int> dist(g.num_v,INT_MAX);
  dist[s] = 0;
  for(std::size_t i=0;i<g.num_v-1;++i){
    for(auto e:g.edges){
      if(dist[e.edge.first] != INT_MAX && dist[e.edge.first] + e.weight < dist[e.edge.second])
        dist[e.edge.second] = dist[e.edge.first] + e.weight;
    }
  }

  for(std::size_t i=0;i<g.num_v-1;++i){
    for(auto e:g.edges){
      if(dist[e.edge.first] == INT_MIN)
        dist[e.edge.second] = INT_MIN;
      // d[v] change in round |V|-1,|V| -> negative cycle
      else if(dist[e.edge.first] != INT_MAX && dist[e.edge.first] + e.weight < dist[e.edge.second])
        dist[e.edge.second] = INT_MIN;
    }
  }
  return dist;
}