WikiGalaxy
Graph Bellman-Ford Algorithm
Introduction to Bellman-Ford Algorithm
The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path from a single source vertex to all other vertices in a weighted graph. It is capable of handling graphs with negative weight edges, unlike Dijkstra's algorithm.
Algorithm Steps
The algorithm initializes the distance to the source vertex as zero and all other vertices as infinity. It then relaxes all edges |V|-1 times, where |V| is the number of vertices. This ensures the shortest paths are calculated even in the presence of negative weight edges.
Handling Negative Weight Cycles
After |V|-1 iterations, the algorithm checks for negative weight cycles. If a shorter path is found, it indicates the presence of a negative weight cycle, which means the graph does not have a solution for shortest paths.
import java.util.*;
class BellmanFord {
static void bellmanFord(int graph[][], int V, int E, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; i++) {
for (int j = 0; j < E; j++) {
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
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[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
static 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;
int graph[][] = {
{ 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 }
};
bellmanFord(graph, V, E, 0);
}
}
Example Explanation
In this example, the graph contains 5 vertices and 8 edges. The Bellman-Ford algorithm is applied starting from vertex 0. The algorithm detects no negative weight cycles, and the shortest path from vertex 0 to all other vertices is printed.
Complexity Analysis
The time complexity of the Bellman-Ford algorithm is O(VE), where V is the number of vertices and E is the number of edges. This makes it less efficient than Dijkstra's algorithm for graphs without negative weights but more versatile for graphs with negative weight edges.
Console Output:
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1
Graph with Negative Weight Cycle
Identifying Negative Weight Cycles
This example demonstrates the Bellman-Ford algorithm's ability to detect negative weight cycles in a graph. Such cycles can cause the shortest path calculation to fail as they reduce the path length indefinitely.
Graph Representation
Consider a graph with 4 vertices and 5 edges, where one of the edges creates a negative weight cycle.
import java.util.*;
class BellmanFordCycle {
static void bellmanFord(int graph[][], int V, int E, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; i++) {
for (int j = 0; j < E; j++) {
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
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[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
static 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 = 4;
int E = 5;
int graph[][] = {
{ 0, 1, 1 }, { 1, 2, -1 },
{ 2, 3, -1 }, { 3, 0, -1 },
{ 0, 2, 4 }
};
bellmanFord(graph, V, E, 0);
}
}
Example Explanation
In this scenario, the Bellman-Ford algorithm identifies a negative weight cycle formed by the edges (0 -> 1 -> 2 -> 3 -> 0). As a result, it outputs a message indicating the presence of a negative weight cycle.
Practical Implications
Detecting negative weight cycles is crucial in applications like currency arbitrage detection or network routing where such cycles can lead to infinite loops or incorrect path calculations.
Console Output:
Graph contains negative weight cycle
Graph with Positive Weights
Using Bellman-Ford on Positive Weights
Although Bellman-Ford is typically used for graphs with negative weights, it can also be applied to graphs with only positive weights. This example illustrates its application in such scenarios.
Graph Structure
Consider a graph with 4 vertices and 4 edges, all with positive weights. The algorithm will compute the shortest path from the source vertex to all other vertices.
import java.util.*;
class BellmanFordPositive {
static void bellmanFord(int graph[][], int V, int E, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; i++) {
for (int j = 0; j < E; j++) {
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
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[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
static 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 = 4;
int E = 4;
int graph[][] = {
{ 0, 1, 4 }, { 0, 2, 5 },
{ 1, 2, 3 }, { 2, 3, 1 }
};
bellmanFord(graph, V, E, 0);
}
}
Example Explanation
In this example, the Bellman-Ford algorithm successfully calculates the shortest path from vertex 0 to all other vertices, showing its versatility in handling graphs with positive weights.
Comparison with Dijkstra's Algorithm
While Dijkstra's algorithm is more efficient for graphs with non-negative weights, Bellman-Ford can serve as an alternative when negative weights are present or for educational purposes.
Console Output:
Vertex Distance from Source 0 0 1 4 2 5 3 6
Graph with Mixed Weights
Mixed Weight Graphs
This example demonstrates the Bellman-Ford algorithm's ability to handle graphs with a mix of positive and negative weights. Such graphs are common in real-world scenarios where costs may vary.
Graph Description
Consider a graph with 5 vertices and 6 edges, where some edges have negative weights. The algorithm calculates the shortest path from a specified source vertex.
import java.util.*;
class BellmanFordMixed {
static void bellmanFord(int graph[][], int V, int E, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; i++) {
for (int j = 0; j < E; j++) {
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
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[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
static 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 = 6;
int graph[][] = {
{ 0, 1, 6 }, { 0, 2, 7 },
{ 1, 2, 8 }, { 1, 3, 5 },
{ 1, 4, -4 }, { 3, 4, 2 }
};
bellmanFord(graph, V, E, 0);
}
}
Example Explanation
In this graph, the Bellman-Ford algorithm effectively computes the shortest paths despite the presence of negative weight edges, demonstrating its robustness in mixed weight scenarios.
Real-World Applications
Mixed weight graphs are typical in transportation networks, financial models, and other systems where costs can fluctuate, making Bellman-Ford a valuable tool for analysis.
Console Output:
Vertex Distance from Source 0 0 1 6 2 7 3 11 4 2
Graph with Multiple Sources
Handling Multiple Source Vertices
The Bellman-Ford algorithm can be adapted to handle scenarios where multiple source vertices are involved. This example shows how to compute shortest paths from multiple sources in a graph.
Graph Setup
Consider a graph with 6 vertices and 7 edges, where we want to find the shortest paths from two different source vertices.
import java.util.*;
class BellmanFordMultipleSources {
static void bellmanFord(int graph[][], int V, int E, int[] sources) {
for (int src : sources) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; i++) {
for (int j = 0; j < E; j++) {
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
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[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
System.out.println("Source Vertex: " + src);
printArr(dist, V);
}
}
static 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 = 6;
int E = 7;
int graph[][] = {
{ 0, 1, 2 }, { 1, 2, 3 },
{ 2, 3, 1 }, { 3, 4, 2 },
{ 4, 5, 3 }, { 0, 3, 4 },
{ 2, 5, 1 }
};
int[] sources = {0, 2};
bellmanFord(graph, V, E, sources);
}
}
Example Explanation
This example demonstrates the calculation of shortest paths from multiple source vertices (0 and 2) using the Bellman-Ford algorithm, highlighting its flexibility in different graph scenarios.
Applications
Such an approach is useful in network design and logistics where multiple starting points need to be considered for path optimization.
Console Output:
Source Vertex: 0 Vertex Distance from Source 0 0 1 2 2 5 3 4 4 6 5 6 Source Vertex: 2 Vertex Distance from Source 0 2147483647 1 2147483647 2 0 3 1 4 3 5 1
