The Bellman-Ford algorithm is a single-source shortest path algorithm based on relaxation operation, which can calculate the shortest path from the source node to all other nodes. Unlike Dijkstra’s algorithm, the Bellman-Ford algorithm can handle graphs containing negative weight edges. The algorithm gradually updates the shortest path estimate of the node in an iterative manner until convergence. If a negative weight cycle exists, the algorithm detects and reports its presence.
Relaxation operation:
The relaxation operation is used to update the shortest path estimate of a node in order to find a shorter path. In the shortest path algorithm, we determine whether the shortest path estimate of the adjacent node needs to be updated by comparing the shortest path estimate of the current node with the sum of the path lengths to the adjacent nodes through the node. If the path length to the adjacent node through the current node is shorter, the shortest path estimate of the adjacent node is updated to the new path length.
Specifically, the steps of the relaxation operation are as follows:
- Get the shortest path estimate of the current node (the shortest path estimate of the starting node is 0) and the neighbor node information of the current node.
- For each neighbor node, calculate the path length from the starting node through the current node to the neighbor node.
- Compare this path length to the neighbor node’s current shortest path estimate.
- If the path length is shorter, the shortest path estimate of the neighbor node is updated to the new path length.
By continuously performing relaxation operations, the shortest path estimate of each node can finally be obtained.
In the Bellman-Ford algorithm, the relaxation operation is applied to all edges in each iteration to ensure that the shortest path estimate of each node is updated correctly. If in the last iteration, there are still nodes whose shortest path estimates change, it means that there is a negative weight cycle in the graph.
In summary, the relaxation operation is a key step in the shortest path algorithm. By comparing the path lengths and updating the shortest path estimate of the node, the shortest path can be found step by step. For an edge (u, v) in the graph, the corresponding formula for the relaxation operation is: dis[v] = min( dis[v] , dis[u] + w(u,v) ). After looping n times, all edges must satisfy dist[b]<=dist[a] + w. This is called "triangle inequality". But note that if there is a negative weight loop in the graph, the shortest path may not exist.
For example:
The blue number represents the weight of the edge. We want to find the shortest path from point 1 to point 5. We walked from 1 to 2, and points 2, 3, and 4 formed a circle. The total weight of the circle is 3 + -2 + -2=-1, then the length of one turn will be reduced by one, so we can make infinite turns, and the total length of infinite turns will become negative infinity. If we go out of the circle, it will still be negative infinity. So if there is a negative weight loop in the graph, the distance from point 1 to point n will become negative infinity and it will not exist.
Idea analysis:
1. Initialize the path from source point s to each point v as dis[v] = ∞, dis[s] = 0.
2. Iterative update: Repeat the following steps until no node’s shortest path estimate changes or the maximum number of iterations is reached:
For each edge in the graph, an attempt is made to perform a relaxation operation through that edge, i.e. update the estimate of the shortest path connecting the nodes.
3. Detect negative weight loops: If there are still nodes whose shortest path estimates change in the last iteration, it means there is a negative weight loop.
As shown in the picture
dis[4] is the shortest distance that requires at most one edge from point 1 to point 4. It can be easily seen from the figure that the shortest distance is 7, which is the distance of 1-2-3-4. .
Code display:
#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f // Macro definition positive infinity
using namespace std;
const int MAXN = 10010; // Maximum number of nodes
vector<vector<pair<int, int>>> adj(MAXN); // Store the adjacency list of the directed weighted graph
int dist[MAXN]; //Storage the shortest distance from the starting point to each node
void BellmanFord(int src, int n) {
//Initialize distance array
for (int i = 0; i < n; i + + ) {
dist[i] = INF;
}
dist[src] = 0; //The distance from the starting point to itself is 0
// Carry out n-1 rounds of relaxation operations
for (int i = 0; i < n - 1; i + + ) {
// For each edge (u, v), try to update the shortest distance from the starting point src to v
for (int u = 0; u < n; u + + ) { // Traverse each node u
for (auto & amp; p : adj[u]) { // Traverse all outgoing edges of node u (p.first is v, p.second is edge weight)
/* auto & amp; p is the syntax for a range-based for loop. It is used to iterate over the elements in a container (e.g. vector, list, map, etc.). auto & amp; p : adj[u] means that for each element in adj[u], assign it to the variable p and perform the corresponding loop body operation. By using the auto keyword, the compiler automatically infers the type of p , while & amp; represents a reference binding to p so that the value of the element can be modified within the body of the loop. */
int v = p.first;
int weight = p.second;
if (dist[u] != INF & amp; & amp; dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
}
}
}
}
// Check if there is a negative weight loop
for (int u = 0; u < n; u + + ) {
for (auto & amp; p : adj[u]) {
int v = p.first;
int weight = p.second;
if (dist[u] != INF & amp; & amp; dist[v] > dist[u] + weight) {
cout << "Graph contains negative weight cycle" << endl;
return;
}
}
}
// Output the shortest distance from the starting point src to each node
for (int i = 0; i < n; i + + ) {
cout << "Shortest distance from " << src << " to " << i << " is " << dist[i] << endl;
}
}
int main() {
int n, m, s; // n represents the number of nodes, m represents the number of edges, and s represents the starting point
cin >> n >> m >> s;
//Input the information of each edge of the directed weighted graph and store it in the adjacency list
for (int i = 0; i < m; i + + ) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
BellmanFord(s, n);
return 0;
}
In this function, we use an adjacency list to store the directed weighted graph, and store the outgoing edge of each node as a pair, where first represents the node connected to the outgoing edge, and second represents the edge weight of the outgoing edge. .
For each node u, we traverse all its outgoing edges (p.first is v, p.second is edge weight), and try to update the shortest distance from the starting point src to v. The specific implementation is to calculate it through dist[u] + weight The distance between src and v. If this distance is smaller than the original stored dist[v], update dist[v].
After n-1 rounds of relaxation operations, we check whether there is a negative weight loop. If it exists, the Bellman-Ford algorithm is not applicable, because the negative weight loop will cause the shortest distance from the starting point to some nodes to be undefined. At this time, we need to output an error message and exit the program. If there is no negative weight loop, output the shortest distance from the starting point src to each node.
Summary: The Bellman-Ford algorithm is a powerful tool for solving the shortest path problem. It can handle graphs containing negative weight edges and is widely used in practice. This blog introduces the principles, application scenarios and a simple implementation example of the Bellman-Ford algorithm. I hope that by reading this blog, you will have a deeper understanding of the Bellman-Ford algorithm and be able to use it flexibly when you need to solve the shortest path problem.