The Bellman-Ford algorithm is a graph traversal algorithm that solves the shortest path problem. It can process most graphs, provided it doesn’t contain a cycle with negative length.
The algorithm works by keeping track of the distances from the starting node to all nodes of the graph. Initially, the distance to the starting node is 0, and to other nodes is infinite. By finding edges that shorten the path, this reduces the distances until it’s not possible to continue reducing.
It relies on passes, i.e., we relax each edge times. From an infinite initial state, it only takes weights that reduce the distance to a given node. The overall time complexity is , because it takes passes and iterates through all edges during a round.
Implementation
for (int i = 1; i <= n; i++) distance[i] = INT_MAX;
distance[x] = 0;
for (int i = 1; i <= n - 1; i++) {
for (auto e: edges) {
int a, b, w;
tie(a, b, w) = e; // tuple of references
distance[b] = min(distance[b], distance[a] + w);
}
}
for (auto e: edges) {
if (e.first > e.second + e.weight) // negative weight cycle
return false;
}
return true;Implications
Bellman-Ford can also check for a cycle with a negative length within the graph. Because of the way BF is structured, we can infinitely shorten any path that contains the cycle by repeating the cycle again and again. If we run it for rounds and the last round reduces distance, the graph contains a negative cycle.