Imagine a weighted graph is given to you. You know where the source vertex is and need to find the shortest path to all the other vertices. What algorithm will you implement to solve this problem? you may decide on Dijkstra’s algorithm. But what if negative weights are also included? Dijkstra can’t solve this problem. We now require a new algorithm. The BellmanFord algorithm is similar to Dijkstra’s algorithm, but it works even when the edge weights are negative. This article discusses the BellmanFord algorithm in detail, including its working, complexity, the difference between Dijkstra’s and BellmanFord algorithms, and applications of the BellmanFord algorithm. Before moving down straight to the BellmanFord algorithm, first, let us see why we should be wary of negative weights in a graph.
Why Should We Be Cautious Of Negative Weights?
Negative weight edges can possibly generate negative weight cycles, this is something to be wary of. A cycle is a closed path with the same vertex at the beginning and end. As a result, a negative cycle becomes a cycle whose total sum of edge weights is negative. Shortest path algorithms cannot detect such cycles and produce incorrect results. This is something that not even the BellmanFord algorithm can overcome. For a better understanding, consider the illustration 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 wellknown algorithm in graph theory that is used to find the shortest path between source and any other vertex in a graph. It is an improvement over Dijkstra’s algorithm, which works only on graphs with nonnegative weights. Bellman Ford algorithm finds the shortest path to all vertices from a single source in O(V*E) time complexity. It can also determine if a negative edge weight cycle occurs in the given graph.
FAQs
Here are some frequently asked questions on the Bellman Ford algorithm.
Q1. Does the Bellman Ford algorithm work with undirected graphs?
Answer: Yes, the Bellman Ford algorithm works with undirected graphs as well as directed graphs.
Q2. How can I detect a negative weight cycle in a graph?
Answer: To detect a negative weight cycle in a graph, you can repeat the Bellman Ford algorithm one more time after iterating V – 1 time. If any distance is updated in this extra iteration, there must be a negative weight cycle in the graph.
Q3. Can the Bellman Ford algorithm handle graphs with negative weights but no negative weight cycles?
Answer: Yes, the Bellman Ford algorithm can handle graphs with negative weights but no negative weight cycles.
Q4. Is the Bellman Ford algorithm guaranteed to find the shortest path in a graph?
Answer: Yes, the Bellman Ford algorithm is guaranteed to find the shortest path in a graph, as long as the graph does not have negative weight cycles.
Q5. Is the Bellman Ford algorithm a greedy algorithm?
Answer: No, the Bellman Ford algorithm is not a greedy algorithm because it does not always choose the locally optimal solution at each step.
Q6. Can the Bellman Ford algorithm handle graphs with disconnected components?
Answer: Yes, the Bellman Ford algorithm can handle graphs with disconnected components. It will find the shortest path from the source vertex to all other vertices in each connected component.
Q7. Is the Bellman Ford algorithm a dynamic programming algorithm?
Answer: Yes, the Bellman Ford algorithm is a dynamic programming algorithm that uses the principle of optimality to find the shortest path.