The Bellman-Ford algorithm is an algorithm for finding the shortest distances from a single source node to all other nodes in a weighted graph. The graph may contain negative weight edges, which makes it different from the Dijkstra's algorithm, which only works on graphs with non-negative edge weights. The algorithm iteratively updates the distances of all nodes in the graph until it converges to the optimal solution.
import java.util.Arrays;
class Edge {
int source, destination, weight;
Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
class BellmanFord {
int vertices, edges;
Edge edge[];
BellmanFord(int vertices, int edges) {
this.vertices = vertices;
this.edges = edges;
edge = new Edge[edges];
for (int i = 0; i < edges; i++) {
edge[i] = new Edge(0, 0, 0);
}
}
void BellmanFordEvaluation(int source) {
int distance[] = new int[vertices];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source] = 0;
for (int i = 1; i < vertices; i++) {
for (int j = 0; j < edges; j++) {
int u = edge[j].source;
int v = edge[j].destination;
int weight = edge[j].weight;
if (distance[u] != Integer.MAX_VALUE &&
distance[v] > distance[u] + weight) {
distance[v] = distance[u] + weight;
}
}
}
for (int j = 0; j < edges; j++) {
int u = edge[j].source;
int v = edge[j].destination;
int weight = edge[j].weight;
if (distance[u] != Integer.MAX_VALUE &&
distance[v] > distance[u] + weight) {
System.out.println("The graph contains negative weight cycle");
}
}
printArr(distance, source);
}
void printArr(int distance[], int source) {
System.out.println("Vertex Distance from Source");
for (int i = 0; i < vertices; ++i) {
System.out.println(source + " to " + i + " is " + distance[i]);
}
}
public static void main(String[] args) {
int vertices = 5;
int edges = 8;
BellmanFord bf = new BellmanFord(vertices, edges);
bf.edge[0] = new Edge(0, 1, -1);
bf.edge[1] = new Edge(0, 2, 4);
bf.edge[2] = new Edge(1, 2, 3);
bf.edge[3] = new Edge(1, 3, 2);
bf.edge[4] = new Edge(1, 4, 2);
bf.edge[5] = new Edge(3, 2, 5);
bf.edge[6] = new Edge(3, 1, 1);
bf.edge[7] = new Edge(4, 3, -3);
bf.BellmanFordEvaluation(0);
}
}
Sample Output
Vertex Distance from Source
0 to 0 is 0
0 to 1 is -1
0 to 2 is 2
0 to 3 is -2
0 to 4 is 1
Explanation: The output shows the shortest distance of each node from the source node (0 in this case). The distance of node 0 from itself is 0. The distance of node 1 from the source node 0 is -1. The distance of node 2 from the source node 0 is 2. The distance of node 3 from the source node 0 is -2. The distance of node 4 from the source node 0 is 1. The distances are calculated by the Bellman-Ford algorithm and represent the minimum weight required to reach that node from the source node.
Comments