Monday, November 30, 2015

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);
}

public void addEdge(int from, int to, double 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);

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 -> 4.0
0 - 2 : distTo -> 2.0
2 - 3 : distTo -> 1.0
3 - 4 : distTo -> -3.0
3 - 5 : distTo -> 4.0