Bellman-Ford Algorithm¶
Single source shortest path with negative weight edges
Suppose that we are given a weighted directed graph
Unlike the Dijkstra algorithm, this algorithm can also be applied to graphs containing negative weight edges . However, if the graph contains a negative cycle, then, clearly, the shortest path to some vertices may not exist (due to the fact that the weight of the shortest path must be equal to minus infinity); however, this algorithm can be modified to signal the presence of a cycle of negative weight, or even deduce this cycle.
The algorithm bears the name of two American scientists: Richard Bellman and Lester Ford. Ford actually invented this algorithm in 1956 during the study of another mathematical problem, which eventually reduced to a subproblem of finding the shortest paths in the graph, and Ford gave an outline of the algorithm to solve this problem. Bellman in 1958 published an article devoted specifically to the problem of finding the shortest path, and in this article he clearly formulated the algorithm in the form in which it is known to us now.
Description of the algorithm¶
Let us assume that the graph contains no negative weight cycle. The case of presence of a negative weight cycle will be discussed below in a separate section.
We will create an array of distances
The algorithm consists of several phases. Each phase scans through all edges of the graph, and the algorithm tries to produce relaxation along each edge
It is claimed that
Implementation¶
Unlike many other graph algorithms, for Bellman-Ford algorithm, it is more convenient to represent the graph using a single list of all edges (instead of
The simplest implementation¶
The constant
struct Edge {
int a, b, cost;
};
int n, m, v;
vector<Edge> edges;
const int INF = 1000000000;
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
for (int i = 0; i < n - 1; ++i)
for (Edge e : edges)
if (d[e.a] < INF)
d[e.b] = min(d[e.b], d[e.a] + e.cost);
// display d, for example, on the screen
}
The check if (d[e.a] < INF)
is needed only if the graph contains negative weight edges: no such verification would result in relaxation from the vertices to which paths have not yet found, and incorrect distance, of the type
A better implementation¶
This algorithm can be somewhat speeded up: often we already get the answer in a few phases and no useful work is done in remaining phases, just a waste visiting all edges. So, let's keep the flag, to tell whether something changed in the current phase or not, and if any phase, nothing changed, the algorithm can be stopped. (This optimization does not improve the asymptotic behavior, i.e., some graphs will still need all
With this optimization, it is generally unnecessary to restrict manually the number of phases of the algorithm to
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
for (;;) {
bool any = false;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = d[e.a] + e.cost;
any = true;
}
if (!any)
break;
}
// display d, for example, on the screen
}
Retrieving Path¶
Let us now consider how to modify the algorithm so that it not only finds the length of shortest paths, but also allows to reconstruct the shortest paths.
For that, let's create another array
Note that the algorithm works on the same logic: it assumes that the shortest distance to one vertex is already calculated, and, tries to improve the shortest distance to other vertices from that vertex. Therefore, at the time of improvement we just need to remember
Following is an implementation of the Bellman-Ford with the retrieval of shortest path to a given node
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
vector<int> p(n, -1);
for (;;) {
bool any = false;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = d[e.a] + e.cost;
p[e.b] = e.a;
any = true;
}
if (!any)
break;
}
if (d[t] == INF)
cout << "No path from " << v << " to " << t << ".";
else {
vector<int> path;
for (int cur = t; cur != -1; cur = p[cur])
path.push_back(cur);
reverse(path.begin(), path.end());
cout << "Path from " << v << " to " << t << ": ";
for (int u : path)
cout << u << ' ';
}
}
Here starting from the vertex
The proof of the algorithm¶
First, note that for all unreachable vertices
Let us now prove the following assertion: After the execution of
In other words, for any vertex
Proof:
Consider an arbitrary vertex
The last thing to notice is that any shortest path cannot have more than
The case of a negative cycle¶
Everywhere above we considered that there is no negative cycle in the graph (precisely, we are interested in a negative cycle that is reachable from the starting vertex
It is easy to see that the Bellman-Ford algorithm can endlessly do the relaxation among all vertices of this cycle and the vertices reachable from it. Therefore, if you do not limit the number of phases to
Hence we obtain the criterion for presence of a cycle of negative weights reachable for source vertex
Moreover, if such a cycle is found, the Bellman-Ford algorithm can be modified so that it retrieves this cycle as a sequence of vertices contained in it. For this, it is sufficient to remember the last vertex
Implementation:¶
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
vector<int> p(n, -1);
int x;
for (int i = 0; i < n; ++i) {
x = -1;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = max(-INF, d[e.a] + e.cost);
p[e.b] = e.a;
x = e.b;
}
}
if (x == -1)
cout << "No negative cycle from " << v;
else {
int y = x;
for (int i = 0; i < n; ++i)
y = p[y];
vector<int> path;
for (int cur = y;; cur = p[cur]) {
path.push_back(cur);
if (cur == y && path.size() > 1)
break;
}
reverse(path.begin(), path.end());
cout << "Negative cycle: ";
for (int u : path)
cout << u << ' ';
}
}
Due to the presence of a negative cycle, for
d[e.b] = max(-INF, d[e.a] + e.cost);
The above implementation looks for a negative cycle reachable from some starting vertex
For more on this topic — see separate article, Finding a negative cycle in the graph.
Shortest Path Faster Algorithm (SPFA)¶
SPFA is a improvement of the Bellman-Ford algorithm which takes advantage of the fact that not all attempts at relaxation will work. The main idea is to create a queue containing only the vertices that were relaxed but that still could further relax their neighbors. And whenever you can relax some neighbor, you should put him in the queue. This algorithm can also be used to detect negative cycles as the Bellman-Ford.
The worst case of this algorithm is equal to the
There are some care to be taken in the implementation, such as the fact that the algorithm continues forever if there is a negative cycle.
To avoid this, it is possible to create a counter that stores how many times a vertex has been relaxed and stop the algorithm as soon as some vertex got relaxed for the
const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;
bool spfa(int s, vector<int>& d) {
int n = adj.size();
d.assign(n, INF);
vector<int> cnt(n, 0);
vector<bool> inqueue(n, false);
queue<int> q;
d[s] = 0;
q.push(s);
inqueue[s] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
inqueue[v] = false;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
if (!inqueue[to]) {
q.push(to);
inqueue[to] = true;
cnt[to]++;
if (cnt[to] > n)
return false; // negative cycle
}
}
}
}
return true;
}
Related problems in online judges¶
A list of tasks that can be solved using the Bellman-Ford algorithm:
- E-OLYMP #1453 "Ford-Bellman" [difficulty: low]
- UVA #423 "MPI Maelstrom" [difficulty: low]
- UVA #534 "Frogger" [difficulty: medium]
- UVA #10099 "The Tourist Guide" [difficulty: medium]
- UVA #515 "King" [difficulty: medium]
- UVA 12519 - The Farnsworth Parabox
See also the problem list in the article Finding the negative cycle in a graph. * CSES - High Score * CSES - Cycle Finding