Last Updated on July 2, 2023 by Mayank Dham
Consider a scenario where you are presented with a weighted graph. Your objective is to determine the shortest path from a given source vertex to all other vertices. Initially, you might consider implementing Dijkstra’s algorithm for this task. However, if the graph contains negative weights, Dijkstra’s algorithm cannot be used. Therefore, we need a different algorithm that can handle such situations. The BellmanFord algorithm is a suitable alternative to Dijkstra’s algorithm as it accommodates negative edge weights.
This article provides a comprehensive discussion of the BellmanFord algorithm. It covers its functionality, complexity, highlights the disparities between Dijkstra’s and BellmanFord algorithms, and presents various applications of the BellmanFord algorithm. Before delving into the details of the BellmanFord algorithm, it is important to understand why negative weights in a graph pose a challenge and warrant caution.
Why Should We Be Cautious Of Negative Weights?
It is important to exercise caution when dealing with negative weight edges in a graph due to the possibility of generating negative weight cycles. Negative weight cycles are cycles that have the same vertex at the beginning and end, and their total sum of edge weights is negative. These cycles pose a challenge for shortest path algorithms as they cannot accurately detect them, leading to incorrect results. Even the BellmanFord algorithm is unable to overcome this limitation. To grasp this concept more clearly, please refer to the illustration provided below.
The vertices B, C, and D in this illustration form a cycle with B as the starting and ending nodes. This cycle also behaves as a negative cycle because the total value is 1.
How BellmanFord Algorithm Works
The BellmanFord algorithm is a singlesource shortestpath algorithm that can handle negative weight edges. It works by iteratively relaxing all edges in the graph, reducing the estimated distance from the source vertex to all other vertices until the actual shortest path is found.
Here are the steps involved in the BellmanFord algorithm:
 Step – 1 Initialize the distance to the source vertex as 0, and the distance to all other vertices as infinity.
 Step – 2 Relax all edges in the graph V – 1 times, where V is the number of vertices in the graph. For each edge (u, v) with weight w, check if the distance from the source vertex to v can be reduced by going through u. If so, update the distance to v to the new, shorter distance.
 Step – 3 Check for negative weight cycles. If there is a negative weight cycle in the graph, the algorithm will never converge and will keep reducing the distance to some vertices with each iteration. To detect such cycles, repeat step 2 one more time. If any distance is updated in this extra iteration, there must be a negative weight cycle in the graph.
 Step – 4 If there is no negative weight cycle, the shortest distance to each vertex from the source vertex has been found.
Dry Run of BellmanFord Algorithm
Let’s dry run the BellmanFord algorithm on an example graph.

Let A be the given source vertex. Except for the distance to the source itself, set all distances to infinity. Because the graph has a total of 5 vertices, all edges must be relaxed 4 times.

Let all edges be processed in the following fashion: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C). (E, D). When we relax all edges for the first time, we get the following distances.

The first round of iteration guarantees to generate all shortest paths which are at most one edge long. When we process all edges a second time, we get the following distances. (The last row shows final values).

The second iteration guarantees to generate all shortest paths which are at most two edges long. All edges are processed two more times by the Bellman Ford algorithm. After the second iteration, the distances are minimized, therefore the third and fourth iterations do not update the distances.
Code for Bellman Ford Algorithm
Let’s go into the implementation of Bellman Ford algorithm for various languages after knowing how Bellman Ford Algorithm actually works.
#include <bits/stdc++.h> using namespace std; struct Edge { int src, dest, weight; }; struct Graph { int V, E; struct Edge* edge; }; struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph; graph>V = V; graph>E = E; graph>edge = new Edge[E]; return graph; } void printArr(int dist[], int n) { printf("Vertex Distance from Source\n"); for (int i = 0; i < n; ++i) printf("%d \t\t %d\n", i, dist[i]); } void BellmanFord(struct Graph* graph, int src) { int V = graph>V; int E = graph>E; int dist[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; for (int i = 1; i <= V  1; i++) { for (int j = 0; j < E; j++) { int u = graph>edge[j].src; int v = graph>edge[j].dest; int weight = graph>edge[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } for (int i = 0; i < E; i++) { int u = graph>edge[i].src; int v = graph>edge[i].dest; int weight = graph>edge[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { printf("Graph contains negative weight cycle"); return; } } printArr(dist, V); return; } int main() { int V = 5; int E = 8; struct Graph* graph = createGraph(V, E); // adding edge 01 (or AB in above dry run) graph>edge[0].src = 0; graph>edge[0].dest = 1; graph>edge[0].weight = 1; // adding edge 02 (or AC in above dry run) graph>edge[1].src = 0; graph>edge[1].dest = 2; graph>edge[1].weight = 4; // adding edge 12 (or BC in above dry run) graph>edge[2].src = 1; graph>edge[2].dest = 2; graph>edge[2].weight = 3; // adding edge 13 (or BD in above dry run) graph>edge[3].src = 1; graph>edge[3].dest = 3; graph>edge[3].weight = 2; // adding edge 14 (or BE in above dry run) graph>edge[4].src = 1; graph>edge[4].dest = 4; graph>edge[4].weight = 2; // adding edge 32 (or DC in above dry run) graph>edge[5].src = 3; graph>edge[5].dest = 2; graph>edge[5].weight = 5; // adding edge 31 (or DB in above dry run) graph>edge[6].src = 3; graph>edge[6].dest = 1; graph>edge[6].weight = 1; // adding edge 43 (or ED in above dry run) graph>edge[7].src = 4; graph>edge[7].dest = 3; graph>edge[7].weight = 3; BellmanFord(graph, 0); return 0; }
import java.io.*; import java.lang.*; import java.util.*; class Graph { class Edge { int src, dest, weight; Edge() { src = dest = weight = 0; } }; int V, E; Edge edge[]; Graph(int v, int e) { V = v; E = e; edge = new Edge[e]; for (int i = 0; i < e; ++i) edge[i] = new Edge(); } void BellmanFord(Graph graph, int src) { int V = graph.V, E = graph.E; int dist[] = new int[V]; for (int i = 0; i < V; ++i) dist[i] = Integer.MAX_VALUE; dist[src] = 0; for (int i = 1; i < V; ++i) { for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) { System.out.println( "Graph contains negative weight cycle"); return; } } printArr(dist, V); } void printArr(int dist[], int V) { System.out.println("Vertex Distance from Source"); for (int i = 0; i < V; ++i) System.out.println(i + "\t\t" + dist[i]); } public static void main(String[] args) { int V = 5; int E = 8; Graph graph = new Graph(V, E); // adding edge 01 (or AB in above dry run) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = 1; // adding edge 02 (or AC in above dry run) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // adding edge 12 (or BC in above dry run) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // adding edge 13 (or BD in above dry run) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // adding edge 14 (or BE in above dry run) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // adding edge 32 (or DC in above dry run) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // adding edge 31 (or DB in above dry run) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // adding edge 43 (or ED in above dry run) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = 3; graph.BellmanFord(graph, 0); } }
class Graph: def __init__(self, vertices): self.V = vertices self.graph = [] def addEdge(self, u, v, w): self.graph.append([u, v, w]) def printArr(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("{0}\t\t{1}".format(i, dist[i])) def BellmanFord(self, src): dist = [float("Inf")] * self.V dist[src] = 0 for _ in range(self.V  1): for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print("Graph contains negative weight cycle") return self.printArr(dist) if __name__ == '__main__': g = Graph(5) g.addEdge(0, 1, 1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, 3) g.BellmanFord(0)
Output:
Vertex Distance from Source
0 0
1 1
2 2
3 2
4 1
Complexity Analysis of BellmanFord Algorithm
The time complexity of the BellmanFord algorithm is O(V*E), where V is the number of vertices and E is the number of edges in the graph. This is because the algorithm relaxes each edge in the graph V1 times.
In the worst case, the algorithm may need to perform one additional relaxation for each vertex in the graph, which would take an additional O(V) time. This can happen when the graph contains a negative weight cycle, which causes the algorithm to keep reducing the distance of vertices along the cycle in each iteration, leading to an infinite negative distance. Thus, the worstcase time complexity of the BellmanFord algorithm is O(VE + V), which simplifies to O(VE).
The space complexity of the algorithm is O(V), as we need to maintain an array of size V to store the distances of each vertex from the source vertex.
Difference Between Dijkstra’s and BellmanFord Algorithm
Here is a table comparing Dijkstra’s and BellmanFord algorithms:
Dijkstra’s Algorithm  BellmanFord Algorithm  

Purpose  To find the shortest path from a single source vertex to all other vertices in a graph with nonnegative edge weights.  To find the shortest path from a single source vertex to all other vertices in a graph with negative or nonnegative edge weights. 
Time Complexity  O(V^2) with a naive implementation or O(E * log V) with a priority queue implementation.  O(V * E) 
Negative edge weights  Cannot handle negative edge weights.  Can handle negative edge weights. 
Negative weight cycles  Cannot handle graphs with negative weight cycles.  Can detect and report graphs with negative weight cycles. 
Implementation  Inspired by the greedy approach.  Inspired by the dynamic programming approach. 
Applications of BellmanFord Algorithm
The BellmanFord algorithm has many practical applications in real life. Here are some mentioned below:
 The BellmanFord algorithm is used in distancevector routing protocols, such as the Routing Information Protocol (RIP) and the Border Gateway Protocol (BGP), to find the shortest path between routers in a network.
 GPS navigation systems use the BellmanFord algorithm to find the shortest route between two locations.
 Airlines use the BellmanFord algorithm to optimize their flight routing and scheduling, taking into account factors such as flight distance, flight time, and airport congestion.
 The BellmanFord algorithm can be used to optimize traffic flow by finding the shortest path between two points on a road network.
 The BellmanFord algorithm is used to optimize supply chain management by finding the shortest path between suppliers, manufacturers, and retailers.
 The BellmanFord algorithm is used in circuit design to optimize the routing of signals between different components of a circuit.
Conclusion
The BellmanFord algorithm is a versatile and important algorithm in graph theory and network routing. It provides a solution to the singlesource shortest path problem, even in graphs with negative edge weights. By allowing for negative weights, it extends the applicability of shortest path algorithms beyond what can be achieved with Dijkstra’s algorithm. Additionally, the BellmanFord algorithm can detect negative cycles in a graph, which is a valuable capability in various network analysis and optimization scenarios.
FAQs related to the BellmanFord algorithm:
Q1: Can the BellmanFord algorithm handle graphs with negative edge weights?
Yes, the BellmanFord algorithm can handle graphs with negative edge weights. It is specifically designed to find the shortest path in such graphs.
Q2: What is the time complexity of the BellmanFord algorithm?
The time complexity of the BellmanFord algorithm is O(V * E), where V is the number of vertices and E is the number of edges in the graph.
Q3: Can the BellmanFord algorithm handle graphs with negative cycles?
The BellmanFord algorithm can detect negative cycles in a graph. However, it cannot accurately compute the shortest path when a negative cycle is present, as it will result in an infinite negative weight.
Q4: How does the BellmanFord algorithm differ from Dijkstra’s algorithm?
The main difference between the BellmanFord algorithm and Dijkstra’s algorithm is that BellmanFord can handle graphs with negative edge weights, whereas Dijkstra’s algorithm cannot. BellmanFord is slower due to its higher time complexity but offers more versatility in terms of graph weights.
Q5: What are some practical applications of the BellmanFord algorithm?
The BellmanFord algorithm finds applications in various areas, including network routing protocols, traffic engineering, resource allocation, robustness analysis of networks, and solving the shortest path problem in graphs with negative weights.
Q6: Are there any limitations or drawbacks of the BellmanFord algorithm?
One limitation of the BellmanFord algorithm is its relatively slower time complexity compared to other algorithms like Dijkstra’s algorithm. It also requires additional iterations to detect negative cycles, making it less efficient in certain scenarios. Additionally, it does not handle graphs with negative cycles when computing shortest paths.