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 Bellman-Ford algorithm is similar to Dijkstra’s algorithm, but it works even when the edge weights are negative. This article discusses the Bellman-Ford algorithm in detail, including its working, complexity, the difference between Dijkstra’s and Bellman-Ford algorithms, and applications of the Bellman-Ford algorithm. Before moving down straight to the Bellman-Ford 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 Bellman-Ford 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 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 well-known 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 non-negative 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.