123456789101112131415161718192021222324252627282930 |
- // 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;
- }
|