notebook/code/BellmanFord.cpp

// Bellman-Ford algorithm
// compute shortest path in a directed graph
// even with negative costs
// find negative cycles
// COMPLEXITY: O(nm)
// USAGE : set dist[*] = INF, dist[src] = 0, nodenum, fill edges
typedef struct Edge{
  int u, v, w;
  Edge(int u, int v, int w) : u(u), v(v), w(w) {}
}Edge;
vector<Edge> edges;
int dist[10000];
int nodenum;
void relax(int u, int v, int w) {
  if(dist[v] > dist[u] + w) {
    dist[v] = dist[u] + w;
    // predecessor[v] = u
  }
}
// return false if there is a negative cycle
bool BellmanFord() {
  int edgenum = edges.size();
  for(int i = 0; i < nodenum-1; i++)
    for(int j = 0; j < edgenum; j++) // (if there is no changes we can break)
      relax(edges[j].u, edges[j].v, edges[j].w);
  for(int i = 0; i < edgenum; i++)
    if(dist[edges[i].u] + edges[i].w < dist[edges[i].v])
      return false;
  return true;
}