Bellman Ford Algorithm

Bellman ford algorithm is used to find shortest weight path from a source vertex to all other vertex in a weighted graph.

Input: Graph and a source vertex.

Output: Shortest distance from the source vertex to all other vertex in that graph. If the graph contains negative weight cycle, then the shortest weight is not calculated.

An advantage of Bellman Ford algorithm over Dijkstra’s algorithm is that, it can calculate shorted weight path even with negative weight edges.

[Negative weight edge and negative weight cycle are two different things. Don’t get confused, as both of these algorithm do not work with negative weight cycle, whereas, Bellman Ford algorithm works with negative weight edge.]

The implementation of Bellman Ford Algorithm is very simple, which includes the following steps:

1. This step initializes distances from source vertex to all other vertex as positive infinity. We created an array dis[] of size |V| and initialized all distanced as infinity except the source vertex index.

2. This step calculates the shortest weighted distance. We iterate over all the edges |V-1| times.

For every edge a-b, we do the following,

If (dis[b] > dis[a] + weight of edge ab), then update (dis[b] as dis[b] = dis[a] + weight of edge ab)

Bellman ford algorithm guarantees the shortest weighted path from a source vertex to all other vertex in at most |V-1| iterations.

The vertex which is connected by 1 edge from source is guaranteed to be calculated in 1st iteration.

Similarly, the vertex with simple path having R number of edges (R is always less than |V|) will be calculated in R number of iterations in the worst case scenario.

Implementation in Java

import java.util.*;
import java.io.*;

// Custom node class for creating an object of a vertex
// with neighbour and weight from that vertex.

class Node {
    int a;
    int b;
    int wt;
    Node(int a, int b, int wt) {
        this.a = a;
        this.b = b;
        this.wt = wt;
    }
}

public class ProgramJava {

    // Adds an edge from vertex (a) to it's neighbour (b)
    // and adge weight (wt).

    static void addEdge(ArrayList<ArrayList<Node>> adjList, int a, int b, int wt) {

        adjList.get(a).add(new Node(a, b, wt));

    }

    static void BellmanFord(ArrayList<ArrayList<Node>> adjList, int V, int E, int src) {

        // Created the array of size V to store distances.

        int[] dis = new int[V];

        // Initialised all weights as Integer.MAX_VALUE (Infinite)

        for (int i = 0; i < V; i++) {
            dis[i] = Integer.MAX_VALUE;
        }

        // Initialising istance from source vertex to source vertex as 0

        dis[src] = 0;

        // Relaxing all vertex |V| - 1 times.

        for (int i = 0; i < V - 1; i++) {
            for (int j = 0; j < V; j++) {
                for (Node node : adjList.get(j)) {

                    if (dis[node.a] != Integer.MAX_VALUE && dis[node.a] + node.wt < dis[node.b]) {
                        dis[node.b] = dis[node.a] + node.wt;
                    }
                }
            }
        }

        // Printing the final answer.

        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i + "\t\t" + dis[i]);
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt();
        int E = sc.nextInt();

        ArrayList<ArrayList<Node>> adjList = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int wt = sc.nextInt();
            addEdge(adjList, a, b, wt);
        }
        BellmanFord(adjList, V, E, 0);
    }
}

Input:

5
8
0 1 -1
0 2 4
1 2 3
3 2 5
1 3 2
3 1 1
1 4 2
4 3 -3

Output:

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