Find single-sourced shortest path - bellman-ford algorithm

Continue the journey from the last blog (http://blueocean-penn.blogspot.com/2015/02/dijkstra-algorithm-implementation.html) about find single-sourced shortest path in a graph, last time I implemented Dijkstra algorithm which can deal with graph with cycle with the constrain of all weights have to be non-negative.

The negative cycle issue is the nemesis for any shortest path graph algorithm, in this post I implemented Bellman-Ford algorithm which can find single-sourced shortest path and report negative cycle if there is one.

The algorithm itself is incredibly simple:

for each vertex in the graph except the source vertex
loop through each edge in the graph
do relaxation on (u, v, w), u, v are the vertex, w is the weight of the edge (u, v)

the following implementation assumes graph represented as adjacent matrix w[][]

/*

* O(VE) algorithm can report negative cycle

*/

int[] bellmanford(int source){

int[] distance = new int[this.size];

int[] parent = new int[this.size];

//initialize

for(int i=0;i<this.size; i++){

distance[i] = Integer.MAX_VALUE;

parent[i] = -1;

}

distance[source] = 0;

parent[source] = -1;

for(int i = 1; i< this.size; i++){

for(int u = 0; u<this.size; u++){

for(int v=0; v<this.size; v++){

if(w[u][v]!=0){//there is edge from u->v

//relaxation

if(distance[v] > distance[u] + w[u][v]){

distance[v] = distance[u] + w[u][v];

parent[v] = u;

}

}

}

}

}

for(int u = 0; u<this.size; u++){

for(int v=0; v<this.size; v++){

if(w[u][v]!=0){//there is edge from u->v

if(distance[v] > distance[u] + w[u][v]){

throw new IllegalStateException("Graph has negative cycle!");

}

}

}

}

return distance;

}