Implement Bellman Ford Algorithm
Problem Statement
Given a weighted directed graph with V vertices and E edges (edges can have negative weights), and a source vertex, find the shortest distance from the source to all other vertices. Also detect if a negative weight cycle exists.
Example:
- Input:
V = 5, src = 0, Edges = [[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]] - Output:
[0, -1, 2, -2, 1]
Noob-Friendly Explanation
Dijkstra's algorithm doesn't work when edges have negative weights. Bellman-Ford to the rescue!
Imagine you're finding the cheapest flights between cities, but some routes give you a REBATE (negative cost). Bellman-Ford handles this by relaxing ALL edges repeatedly.
Relaxation means: "Can I get to vertex B cheaper by going through vertex A?" If yes, update the distance to B.
The key insight: the shortest path between any two vertices has at most V-1 edges. So we relax all edges V-1 times. If after V-1 rounds we can still find a shorter path, there's a negative cycle (an infinite discount loop!).
Approach 1: Brute Force (Relax All Edges Per Vertex Update)
Intuition
For each vertex, try relaxing all edges from scratch. Repeat this process until no more updates happen. This is less structured and may do redundant work.
Algorithm
- Initialize distances to infinity, source to 0.
- Keep relaxing edges until no update occurs.
- Check for negative cycles with one more pass.
import java.util.Arrays;
public class BellmanFordBruteForce {
public static int[] bellmanFord(int V, int[][] edges, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
boolean updated = true;
int iterations = 0;
// Keep relaxing until no changes or V-1 iterations
while (updated && iterations < V - 1) {
updated = false;
iterations++;
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
// Also try relaxing reverse combinations (brute force approach)
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
}
// Check for negative cycle
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
System.out.println("Negative weight cycle detected!");
return new int[]{};
}
}
return dist;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1,-1},{0,2,4},{1,2,3},{1,3,2},{1,4,2},{3,2,5},{3,1,1},{4,3,-3}};
int[] result = bellmanFord(V, edges, 0);
System.out.println(Arrays.toString(result)); // [0, -1, 2, -2, 1]
}
}Complexity Analysis
- Time Complexity: O(V × E^2) — redundant relaxation passes make this less efficient.
- Space Complexity: O(V) — for the distance array.
Approach 2: Optimal (Standard Bellman-Ford)
Intuition
Relax ALL edges exactly V-1 times. In iteration i, we find shortest paths using at most i edges. After V-1 iterations, all shortest paths are found. One more pass detects negative cycles.
Algorithm
- Initialize distances to infinity, source to 0.
- Repeat V-1 times: relax all edges.
- Do one more pass: if any distance can still be reduced, negative cycle exists.
import java.util.Arrays;
public class BellmanFordOptimal {
public static int[] bellmanFord(int V, int[][] edges, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// Relax all edges V-1 times
for (int i = 0; i < V - 1; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Check for negative weight cycle (V-th relaxation)
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
System.out.println("Graph contains a negative weight cycle!");
return new int[]{};
}
}
return dist;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1,-1},{0,2,4},{1,2,3},{1,3,2},{1,4,2},{3,2,5},{3,1,1},{4,3,-3}};
int[] result = bellmanFord(V, edges, 0);
System.out.println(Arrays.toString(result)); // [0, -1, 2, -2, 1]
}
}Complexity Analysis
- Time Complexity: O(V × E) — V-1 iterations, each processing all E edges.
- Space Complexity: O(V) — for the distance array.