The Bellman-Ford algorithm emulates the shortest paths from a single source vertex to all other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem but more versatile because it can handle graphs with some edge weights that are negative numbers. Alfonso Shimbel proposed the algorithm in 1955, but it is now named after Richard Bellman and Lester Ford Jr., who brought it out in 1958 and 1956. In 1959, Edward F. Moore published a variation of the algorithm, sometimes referred to as the Bellman-Ford–Moore algorithm.
What Is the Bellman-Ford Algorithm?
Dynamic Programming is used in the Bellman-Ford algorithm. It begins with a starting vertex and calculates the distances between other vertices that a single edge can reach. It then searches for a path with two edges, and so on. The Bellman-Ford algorithm uses the bottom-up approach.
Based on the "Principle of Relaxation," more accurate values gradually recovered an approximation to the proper distance until finally reaching the optimum solution.
Negative weight edges can generate negative weight cycles, which reduce the total path distance by returning to the same point.
Why Should You Be Cautious With Negative Weights?
When attempting to find the shortest path, negative weight cycles may produce an incorrect result.
Shortest path algorithms, such as Dijkstra's Algorithm that cannot detect such a cycle, may produce incorrect results because they may go through a negative weight cycle, reducing the path length.
After learning about the Bellman-Ford algorithm, you will look at how it works in this tutorial.
How Does the Bellman-Ford Algorithm Work?
The Bellman-Ford algorithm works by grossly underestimating the length of the path from the starting vertex to all other vertices. The algorithm then iteratively relaxes those estimates by discovering new ways that are shorter than the previously overestimated paths.
You can ensure that the result is optimized by repeating this process for all vertices.
Step 1: Make a list of all the graph's edges. This is simple if an adjacency list represents the graph.
Step 2: "V - 1" is used to calculate the number of iterations. Because the shortest distance to an edge can be adjusted V - 1 time at most, the number of iterations will increase the same number of vertices.
Step 3: Begin with an arbitrary vertex and a minimum distance of zero. Because you are exaggerating the actual distances, all other nodes should be assigned infinity.
For each edge u-v, relax the path lengths for the vertices:
If distance[v] is greater than distance[u] + edge weight uv, then
distance[v] = distance[u] + edge weight uv
Step 4:If the new distance is less than the previous one, update the distance for each Edge in each iteration. The distance to each node is the total distance from the starting node to this specific node.
Step 5: To ensure that all possible paths are considered, you must consider alliterations. You will end up with the shortest distance if you do this.
Moving ahead with this tutorial on the Bellman-Ford algorithm, you will now learn the pseudocode for this algorithm.
Pseudocode of the Bellman-Ford Algorithm
Every Vertex's path distance must be maintained. That can be stored in a V-dimensional array, where V is the number of vertices.
Not only do you need to know the length of the shortest path, but you also need to be able to find it. To accomplish this, you must map each Vertex to the Vertex that most recently updated its path length.
When the algorithm is finished, you can find the path from the destination vertex to the source.
|
function bellmanFordAlgorithm(G, s) //G is the graph and s is the source vertex for each vertex V in G dist[V] <- infinite // dist is distance prev[V] <- NULL // prev is previous dist[s] <- 0 for each vertex V in G for each edge (u,v) in G temporaryDist <- dist[u] + edgeweight(u, v) if temporaryDist < dist[v] dist[v] <- temporaryDist prev[v] <- u for each edge (U,V) in G If dist[U] + edgeweight(U, V) < dist[V} Error: Negative Cycle Exists return dist[], previ[] |
As you progress through this tutorial, you will see an example of the Bellman-Ford algorithm for a better learning experience.
An Example of Bellman-Ford Algorithm
Consider the weighted graph below.
- Choose path value 0 for the source vertex and infinity for all other vertices.
- If the new calculated path length is less than the previous path length, go to the source vertex's neighboring Edge and relax the path length of the adjacent Vertex.
- This procedure must be repeated V-1 times, where V is the number of vertices in total. This happened because, in the worst-case scenario, any vertex's path length can be changed N times to an even shorter path length.
- As a result, after V-1 iterations, you find your new path lengths and can determine in case the graph has a negative cycle or not.
You will now look at the time and space complexity of the Bellman-Ford algorithm after you have a better understanding of it.
The Complexity of Bellman-Ford Algorithm
Following is the time complexity of the bellman ford algorithm
For all cases, the complexity of this algorithm will be determined by the number of edge comparisons.
|
if temporaryDist < dist[v] |
Edge relaxation differences depend on the graph and the sequence of looking in on edges in the graph.
The algorithm may need to undergo all repetitions while updating edges, but in many cases, the result is obtained in the first few iterations, so no updates are required.
|
dist[v] <- temporaryDist |
-
Worst-Case Time Complexity
When you come across a negative cycle in the graph, you can have a worst-case scenario.
As an example of a negative cycle, consider the following:
In a complete graph with edges between every pair of vertices, and assuming you found the shortest path in the first few iterations or repetitions but still go on with edge relaxation, you would have to relax |E| * (|E| - 1) / 2 edges, (|V| - 1) number of times.
The worst-case scenario in the case of a complete graph, the time complexity is as follows:
O(|V|2) = O(E V). O(|V|) = O (V3)
-
Average Case Time Complexity
You can reduce the worst-case running time by stopping the algorithm when no changes are made to the path values. As a result, there will be fewer iterations.
Another way to improve it is to ignore any vertex V with a distance value that has not changed since the last relaxation in subsequent iterations, reducing the number of edges that need to be relaxed and increasing the number of edges with correct values after each iteration. More information is available at the link at the bottom of this post.
Relaxation occurs |V| - 1 time for every |E| the number of edges, so you multiply the two and get the average, which is the quadratic time complexity of O. (E V).
Automation Test Engineer Master's Program
To learn about the automation of web applicationsExplore Course
-
Best Case Time Complexity
If edge relaxation occurs from left to right in the above graph, the algorithm would only need to perform one relaxation iteration to find the shortest path, resulting in the time complexity of O(E) corresponding to the number of edges in the graph.
The following is the space complexity of the bellman ford algorithm:
The space complexity of the Bellman-Ford algorithm is O(V).
Following that, in this Bellman-Ford algorithm tutorial, you will look at some use cases of the Bellman-Ford algorithm.
Uses of Bellman-Ford Algorithm
There are several real-world applications for the Bellman-Ford algorithm, including:
- Identifying negative weight cycles
- In a chemical reaction, calculate the smallest possible heat gain/loss.
- Identifying the most efficient currency conversion method.
You will now peek at some applications of the Bellman-Ford algorithm in this tutorial.
Applications of the Bellman-Ford Algorithm
Following are the applications of the bellman ford algorithm:
- Examining a graph for the presence of negative weight cycles.
- Using negative weights, find the shortest path in a graph.
- Routing is a concept used in data networks.
Last but not least, you will need to perform practical demonstrations of the Bellman-Ford algorithm in the C programming language.
Code Demonstration of Bellman-Ford Algorithm
|
#include<stdio.h> #include<stdlib.h> #include<conio.h> #include<string.h> #include<limits.h> struct Edges { // This structure is equal to an edge. Edge contains two endpoints. These edges are directed edges so they //contain source and destination and some weight. These 3 are elements in this structure int src, dest, wt; }; // a structure to represent a graph struct Graph { int Vertex, Edge; //Vertex is the number of vertices, and Edge is the number of edges struct Edges* edge; // This structure contains another structure that we have already created. }; struct Graph* designGraph(int Vertex, int Edge) { struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph)); //Allocating space to structure graph graph->Vertex = Vertex; //assigning values to structure elements that taken form user. graph->Edge = Edge; graph->edge = (struct Edges*) malloc( graph->Edge * sizeof( struct Edges ) ); //Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges return graph; } void Solution(int dist[], int n) { // This function prints the last solution printf("\nVertex\tDistance from Source Vertex\n"); int i; for (i = 0; i < n; ++i){ printf("%d \t\t %d\n", i, dist[i]); } } void BellmanFordalgorithm(struct Graph* graph, int src) { int Vertex = graph->Vertex; int Edge = graph->Edge; int Distance[Vertex]; int i,j; // This is the initial step that we know, and we initialize all distances to infinity except the source vertex. // We assign source distance as 0 for (i = 0; i < Vertex; i++) Distance[i] = INT_MAX; Distance[src] = 0; //The shortest path of graph that contain Vertex vertices, never contain "Veretx-1" edges. So we do here "Vertex-1" relaxations for (i = 1; i <= Vertex-1; i++) { for (j = 0; j < Edge; j++) { int u = graph->edge[j].src; int v = graph->edge[j].dest; int wt = graph->edge[j].wt; if (Distance[u] + wt < Distance[v]) Distance[v] = Distance[u] + wt; } } //, up to now, the shortest path found. But BellmanFordalgorithm checks for negative edge cycles. In this step, we check for that // shortest path if the graph doesn't contain any negative weight cycle in the graph. // If we get a shorter path, then there is a negative edge cycle. for (i = 0; i < Edge; i++) { int u = graph->edge[i].src; int v = graph->edge[i].dest; int wt = graph->edge[i].wt; if (Distance[u] + wt < Distance[v]) printf("This graph contains negative edge cycle\n"); } Solution(Distance, Vertex); return; } int main() { int V,E,S; //V = no.of Vertices, E = no.of Edges, S is source vertex printf("Enter number of vertices\n"); scanf("%d",&V); printf("Enter number of edges\n"); scanf("%d",&E); printf("Enter the source vertex number\n"); scanf("%d",&S); struct Graph* graph = designGraph(V, E); //calling the function to allocate space to these many vertices and edges int i; for(i=0;i<E;i++){ printf("\nEnter edge %d properties Source, destination, weight respectively\n",i+1); scanf("%d",&graph->edge[i].src); scanf("%d",&graph->edge[i].dest); scanf("%d",&graph->edge[i].wt); } BellmanFordalgorithm(graph, S); //passing created graph and source vertex to BellmanFord Algorithm function return 0; } |
Output
Now that you have reached the end of the Bellman-Ford tutorial, you will go over everything you’ve learned so far.
Advance your career as a MEAN stack developer with the Post Graduate Program In Full Stack Web Development. Enroll now!
Next Steps
In this Bellman-Ford algorithm tutorial, you looked at what the algorithm is and how it works. You studied and comprehended the Bellman-Ford algorithm step-by-step, using the example as a guide. You also learned C programming language code and the output for calculating the distance from the source vertex in a weighted graph. And you saw the time complexity for applying the algorithm and the applications and uses that you can put to use in your daily lives.
Assume you're looking for a more in-depth study that goes beyond Mobile and Software Development and covers today's most in-demand programming languages and skills. In that case, Simplilearn's software-development course is the right choice for you. Explore this globally recognized Bootcamp program. Rest assured that completing it will be the best decision you can make to enter and advance in the mobile and software development professions.
Do you have any queries about this tutorial on Bellman-Ford Algorithm? Please leave them in the comments section at the bottom of this page if you do. Our experts will be happy to respond to your questions as earliest as possible!
