Algorithm
Bellman-Ford's algorithm is a single-source shortest path algorithm that can handle graphs with negative edge weights. It was proposed by Richard Bellman and Lester Ford, Jr. It works for both directed and undirected graphs and is particularly useful when there are negative weight edges.
Here's a high-level overview of how the Bellman-Ford algorithm works:
-
Initialization: Initialize the distance from the source vertex to all other vertices as infinity, except the distance to the source itself, which is set to 0.
-
Relaxation: Iterate through all edges of the graph repeatedly. In each iteration, attempt to improve the distance values by relaxing the edges. For each edge (u, v) with weight w, if the distance to the destination vertex v can be shortened by taking the edge (u, v), update the distance to v as the sum of the distance to u and the weight w.
-
Detection of Negative Cycles: After performing the relaxation step for all edges for V-1 iterations (where V is the number of vertices), if further relaxation is possible, then there is a negative weight cycle in the graph. The algorithm can be used to detect negative cycles by running an additional iteration. If any distance can be further improved, then a negative cycle exists.
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. The space complexity is O(V).
It's important to note that while Bellman-Ford is a versatile algorithm that can handle graphs with negative edges, it may not work correctly if there is a negative cycle reachable from the source vertex. In such cases, the algorithm may not converge to the correct shortest paths because it will keep reducing the distances indefinitely due to the negative cycle.
Code Examples
#1 Bellman Ford's Algorithm implement in Python
Code -
Python Programming
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def bellman_ford(self, src):
# Initialize distance from source to all other vertices as infinity
dist = [float("inf")] * self.V
dist[src] = 0
# Relax all edges |V| - 1 times
for _ in range(self.V - 1):
# Update dist value and parent index of the adjacent vertices of the picked vertex.
for u, v, w in self.graph:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative-weight cycles
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.print_solution(dist)
def print_solution(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print(f"{i}\t\t{dist[i]}")
# Example Usage
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)
Copy The Code &
Try With Live Editor
#2 Bellman Ford's Algorithm implement in Java
Code -
Java Programming
import java.util.Arrays;
class BellmanFord {
static class Edge {
int source, destination, weight;
Edge() {
source = destination = weight = 0;
}
}
int V, E;
Edge edge[];
BellmanFord(int v, int e) {
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
void BellmanFordAlgorithm(BellmanFord graph, int source) {
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from the source to all other vertices as INFINITE
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// Step 2: Relax all edges |V| - 1 times
for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].source;
int v = graph.edge[j].destination;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// Step 3: Check for negative-weight cycles
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].source;
int v = graph.edge[j].destination;
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;
}
}
// Print the calculated distances
printSolution(dist, source);
}
void printSolution(int dist[], int source) {
System.out.println("Vertex \t 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; // Number of vertices in the graph
int E = 8; // Number of edges in the graph
BellmanFord graph = new BellmanFord(V, E);
// Example graph edges with weights
graph.edge[0].source = 0;
graph.edge[0].destination = 1;
graph.edge[0].weight = -1;
graph.edge[1].source = 0;
graph.edge[1].destination = 2;
graph.edge[1].weight = 4;
graph.edge[2].source = 1;
graph.edge[2].destination = 2;
graph.edge[2].weight = 3;
graph.edge[3].source = 1;
graph.edge[3].destination = 3;
graph.edge[3].weight = 2;
graph.edge[4].source = 1;
graph.edge[4].destination = 4;
graph.edge[4].weight = 2;
graph.edge[5].source = 3;
graph.edge[5].destination = 2;
graph.edge[5].weight = 5;
graph.edge[6].source = 3;
graph.edge[6].destination = 1;
graph.edge[6].weight = 1;
graph.edge[7].source = 4;
graph.edge[7].destination = 3;
graph.edge[7].weight = -3;
int source = 0;
graph.BellmanFordAlgorithm(graph, source);
}
}
Copy The Code &
Try With Live Editor
#3 Bellman Ford's Algorithm implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Define a structure to represent a directed edge
struct Edge {
int src, dest, weight;
};
// Define a structure to represent a graph
struct Graph {
int V, E; // Number of vertices and edges
struct Edge* edge; // Array to store edges
};
// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}
// Function to print the distance array
void printDistances(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]);
}
// Bellman-Ford algorithm
void bellmanFord(struct Graph* graph, int src) {
int V = graph->V;
int E = graph->E;
int dist[V];
// Initialize distances from the source to all other vertices as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Relax all edges V-1 times
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;
}
}
// Check for negative-weight cycles
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.\n");
return;
}
}
// Print the distance array
printDistances(dist, V);
}
// Driver program to test the above functions
int main() {
int V = 5; // Number of vertices
int E = 8; // Number of edges
struct Graph* graph = createGraph(V, E);
// Edges of the graph
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
int src = 0; // Source vertex
bellmanFord(graph, src);
return 0;
}
Copy The Code &
Try With Live Editor
#4 Bellman Ford's Algorithm implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Edge {
int src, dest, weight;
};
class Graph {
int V, E;
vector < Edge> edges;
public:
Graph(int V, int E) : V(V), E(E) {}
void addEdge(int src, int dest, int weight) {
edges.push_back({src, dest, weight});
}
void bellmanFord(int src) {
vector<int> distance(V, numeric_limits < int>::max());
distance[src] = 0;
// Relax all edges V-1 times
for (int i = 0; i < V - 1; ++i) {
for (const auto& edge : edges) {
if (distance[edge.src] != numeric_limits<int>::max() &&
distance[edge.src] + edge.weight < distance[edge.dest]) {
distance[edge.dest] = distance[edge.src] + edge.weight;
}
}
}
// Check for negative weight cycles
for (const auto& edge : edges) {
if (distance[edge.src] != numeric_limits < int>::max() &&
distance[edge.src] + edge.weight < distance[edge.dest]) {
cout << "Graph contains negative weight cycle!" << endl;
return;
}
}
// Print the distances
cout << "Shortest distances from source " << src << " are:" << endl;
for (int i = 0; i < V; ++i) {
cout << "To vertex " << i << ": " << distance[i] << endl;
}
}
};
int main() {
int V, E;
cout << "Enter the number of vertices and edges: ";
cin >> V >> E;
Graph graph(V, E);
cout << "Enter the edges (src, dest, weight):" << endl;
for (int i = 0; i < E; ++i) {
int src, dest, weight;
cin >> src >> dest >> weight;
graph.addEdge(src, dest, weight);
}
int src;
cout << "Enter the source vertex: ";
cin >> src;
graph.bellmanFord(src);
return 0;
}
Copy The Code &
Try With Live Editor
Demonstration
Bellman Ford's Data Structure and Algorithm