notebook/code/BellmanFord.cpp

// Bellman-Ford algorithm
// compute shortest path in a directed graphdefaults
// even with negative coststypede
// find negative cycles
// COMPLEXITY: O(nm)
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, edgenum;
const int INF = 1000000000;
// set dest[*] = INF, dist[src] = 0
// fill edges, nodenum, edgenum
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() {
	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;
}