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.