Bellman-Ford Single Source Shortest Paths Algorithm - Java

The idea is simple - relax all the edges V-1 number of times.

Proof - 

Path-relaxation property - If p = {v0, v1, ..., vk) is a shortest path from s = v0 to vk, and we relax the edges of p in the order (v0, v1), (v1, v2), ..., (vk-1, vk), then vk.d = f(s, vk). This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of p.

Let us consider we have a graph with 5 vertices and 8 edges. Relaxations are as follows (we set the source as vertex 0 from where we have to find the shortest path to all other vertices):

Let us say

The shortest path from Vertex 0 to Vertex 1 needs relaxations in the order E2 E4 E1 E0
The shortest path from Vertex 0 to Vertex 2 needs relaxations in the order E3 E8 E6

The shortest path from Vertex 0 to Vertex 3 needs relaxations in the order E2 E0 E8

The shortest path from Vertex 0 to Vertex 4 needs relaxations in the order E3 E1

Pass 1 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 2 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 3 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 4 E0 E1 E2 E3 E4 E5 E6 E7 E8

The highlighted edges shows that the shortest path edges for vertex 0 to vertex 1 has been relaxed. You can trace out the edge relaxations for other paths as well.

Example for Worst Case (Wikipedia) -

Source:

import java.util.ArrayList;
import java.util.Arrays;

public class BellmanFord {
    
    class DWEdge{
        int from, to;
        double weight;

        DWEdge(int from, int to, double weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }   
    
    private ArrayList<ArrayList<DWEdge>> graph;
    private int edgeTo[];
    private double distTo[];
    private int V;
    
    BellmanFord(int V){
        graph = new ArrayList<>();
        edgeTo = new int[V];
        distTo = new double[V]; Arrays.fill(distTo, Double.POSITIVE_INFINITY);
        this.V = V;
        
        graph.ensureCapacity(V);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
    }
    
    public void addEdge(int from, int to, double weight){
        graph.get(from).add(new DWEdge(from, to, weight));
    }
    
    public void relax(DWEdge e){  
        if(distTo[e.to] > distTo[e.from] + e.weight){ 
            distTo[e.to] = distTo[e.from] + e.weight; 
            edgeTo[e.to] = e.from; 
        }
    }
      
    public void BellmanFord(int source){
        distTo[source] = 0;
        
        for(int i=0;i<V-1;++i){ 
            for(int j=0;j<V;++j){
                for(DWEdge e:graph.get(j)){
                    relax(e);
                }
            }
        }
    }
    
    
    public static void main(String[] args){
        BellmanFord bf = new BellmanFord(6);
        bf.addEdge(0,1,4);bf.addEdge(0,2,2);
        bf.addEdge(3,4,-4);bf.addEdge(0,3,2);
        bf.addEdge(2,3,-1);bf.addEdge(1,2,3);
        bf.addEdge(1,4,1);bf.addEdge(4,2,6);
        bf.addEdge(1,5,5);bf.addEdge(3,5,3);
        bf.addEdge(5,4,7);
        
        int source = 0;
        bf.BellmanFord(source);
        
        System.out.println("Results : ");
        for(int i=0;i<bf.V;++i){
            if(i==source)continue;
            System.out.println(bf.edgeTo[i]+" - "+i+" : distTo["+i+"] -> "+bf.distTo[i]);
        }
    }
}

Output:

Results :
0 - 1 : distTo[1] -> 4.0
0 - 2 : distTo[2] -> 2.0
2 - 3 : distTo[3] -> 1.0
3 - 4 : distTo[4] -> -3.0
3 - 5 : distTo[5] -> 4.0