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 Bellman-Ford algorithm is a suitable alternative to Dijkstra’s algorithm as it accommodates negative edge weights.
This article provides a comprehensive discussion of the Bellman-Ford algorithm. It covers its functionality, complexity, highlights the disparities between Dijkstra’s and Bellman-Ford algorithms, and presents various applications of the Bellman-Ford algorithm. Before delving into the details of the Bellman-Ford 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 Bellman-Ford 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 Bellman-Ford Algorithm Works
The Bellman-Ford algorithm is a single-source shortest-path 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 Bellman-Ford 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 Bellman-Ford Algorithm
Let’s dry run the Bellman-Ford 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 0-1 (or A-B in above dry run)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
// adding edge 0-2 (or A-C in above dry run)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
// adding edge 1-2 (or B-C in above dry run)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
// adding edge 1-3 (or B-D in above dry run)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
// adding edge 1-4 (or B-E in above dry run)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
// adding edge 3-2 (or D-C in above dry run)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
// adding edge 3-1 (or D-B in above dry run)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// adding edge 4-3 (or E-D 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 0-1 (or A-B in above dry run)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// adding edge 0-2 (or A-C in above dry run)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// adding edge 1-2 (or B-C in above dry run)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// adding edge 1-3 (or B-D in above dry run)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// adding edge 1-4 (or B-E in above dry run)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// adding edge 3-2 (or D-C in above dry run)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// adding edge 3-1 (or D-B in above dry run)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// adding edge 4-3 (or E-D 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 1Complexity Analysis of Bellman-Ford Algorithm
The time complexity of the Bellman-Ford 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 V-1 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 worst-case time complexity of the Bellman-Ford 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 Bellman-Ford Algorithm
Here is a table comparing Dijkstra’s and Bellman-Ford algorithms:
| Dijkstra’s Algorithm | Bellman-Ford Algorithm | |
|---|---|---|
| Purpose | To find the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. | To find the shortest path from a single source vertex to all other vertices in a graph with negative or non-negative 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 Bellman-Ford Algorithm
The Bellman-Ford algorithm has many practical applications in real life. Here are some mentioned below:
- The Bellman-Ford algorithm is used in distance-vector 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 Bellman-Ford algorithm to find the shortest route between two locations.
- Airlines use the Bellman-Ford algorithm to optimize their flight routing and scheduling, taking into account factors such as flight distance, flight time, and airport congestion.
- The Bellman-Ford algorithm can be used to optimize traffic flow by finding the shortest path between two points on a road network.
- The Bellman-Ford algorithm is used to optimize supply chain management by finding the shortest path between suppliers, manufacturers, and retailers.
- The Bellman-Ford algorithm is used in circuit design to optimize the routing of signals between different components of a circuit.
Conclusion
The Bellman-Ford algorithm is a versatile and important algorithm in graph theory and network routing. It provides a solution to the single-source 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 Bellman-Ford algorithm can detect negative cycles in a graph, which is a valuable capability in various network analysis and optimization scenarios.
FAQs related to the Bellman-Ford algorithm:
Q1: Can the Bellman-Ford algorithm handle graphs with negative edge weights?
Yes, the Bellman-Ford 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 Bellman-Ford algorithm?
The time complexity of the Bellman-Ford 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 Bellman-Ford algorithm handle graphs with negative cycles?
The Bellman-Ford 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 Bellman-Ford algorithm differ from Dijkstra’s algorithm?
The main difference between the Bellman-Ford algorithm and Dijkstra’s algorithm is that Bellman-Ford can handle graphs with negative edge weights, whereas Dijkstra’s algorithm cannot. Bellman-Ford 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 Bellman-Ford algorithm?
The Bellman-Ford 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 Bellman-Ford algorithm?
One limitation of the Bellman-Ford 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.