# 1. Introduction

The *Bellman-Ford* algorithm is used to find the shortest path from a single source vertex to all other vertices in a weighted graph. It is capable of handling graphs in which some of the edge weights are negative numbers.

# 2. Program Steps

1. Initialize the distance to the source vertex as 0 and to all other vertices as infinity.

2. For each vertex, apply relaxation for all the edges.

3. Do the above step *V-1* times where *V* is the number of vertices.

4. For detecting negative cycles, run a relaxation step once more for each edge. If we can get a shorter path, then there is a cycle.

# 3. Code Program

```
class BellmanFordAlgorithm {
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
BellmanFordAlgorithm(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(int src) {
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 = edge[j].src;
int v = edge[j].dest;
int weight = 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 = edge[j].src;
int v = edge[j].dest;
int weight = 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;
BellmanFordAlgorithm bfa = new BellmanFordAlgorithm(V, E);
bfa.edge[0].src = 0;
bfa.edge[0].dest = 1;
bfa.edge[0].weight = -1;
bfa.edge[1].src = 0;
bfa.edge[1].dest = 2;
bfa.edge[1].weight = 4;
bfa.edge[2].src = 1;
bfa.edge[2].dest = 2;
bfa.edge[2].weight = 3;
bfa.edge[3].src = 1;
bfa.edge[3].dest = 3;
bfa.edge[3].weight = 2;
bfa.edge[4].src = 1;
bfa.edge[4].dest = 4;
bfa.edge[4].weight = 2;
bfa.edge[5].src = 3;
bfa.edge[5].dest = 2;
bfa.edge[5].weight = 5;
bfa.edge[6].src = 3;
bfa.edge[6].dest = 1;
bfa.edge[6].weight = 1;
bfa.edge[7].src = 4;
bfa.edge[7].dest = 3;
bfa.edge[7].weight = -3;
bfa.BellmanFord(0);
}
}
```

### Output:

Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1

# 4. Step By Step Explanation

1. *Edge*: Represents a directed edge with a source, destination, and weight.

2. *BellmanFord*: The main function to find the shortest path. It consists of the primary logic for the Bellman-Ford algorithm.

3. *printArr*: Utility function to print distances.

4. The main function initializes a graph, sets up its edges, and their weights, and then calls *BellmanFord*.