Implementation of Bellman Ford Algorithm.

/*
ALGORITHM (Borrowed from wiki)
==============================
procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices and edges,
   // and fills two arrays (distance and predecessor) with shortest-path information

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"


BELLMAN FORD VS DIJKSTRA
========================
1.      Bellman Ford runs in O(VE) time where as Dijkstra can be optimized to run in O(VlogV) time with use of Fibonacci heap.
2.      Bellman ford works on negative weight graphs as well where as Dijkstra doesn’t allow negative weight edges.
3.      Dijkstra algorithm is highly centric and is not very distributive. Dijkstra is good if all data is stored on one machine’s main memory.

COMPLEXITY
==========
O(VE)
*/

public void bellmanFord(int sourceVertex) {
      int i,j,cost;
      Vertex source,target;
      boolean negativeCycle = false;
      int distance[] = new int[totalVertices];

      // Step 1: initialize graph
      //Set distance of each vertex from source to INF and distance source = 0
      for(i=0; i<totalVertices; i++)
            distance[i] = INF;
      distance[sourceVertex] = 0;
      
      // Step 2: relax edges repeatedly
      //Relax each edge by 1,2...|V|-1 
      //Complexity : O(|V|).
      //Longest cycle free path between 2 vertices can have atmost |v|-1 edges.
      for(i=0; i<totalVertices-1; i++) {            
            //Explore each edge. Complexity : O(|E|) 
            for(j=0; j<totalVertices; j++) {
                  source = vertices[j];
                  for(Edge e : source.edges) {                  
                        target = e.Target;
                        cost = distance[source.vertexId] + e.weight;
                        
                  //If current distance is greater than new reachable distance.
                  //then update distance.
                        if(distance[target.vertexId] > cost) {
                              distance[target.vertexId] =  cost;
                        }
                  }
            }
      }
      // Step 3: check for negative-weight cycles
      //Detect negative weight cycles by relaxing to |V| edges.
      //If there is a negative cycle in the path then simply report it.
      for(j=0; j<totalVertices; j++) {
            source = vertices[j];
            for(Edge e : source.edges) {
                  target = e.Target;
                  cost = distance[source.vertexId] + e.weight;
                  if(distance[target.vertexId] > cost) {
                        negativeCycle = true;
                        System.out.println("NEGATIVE WEIGHT CYCLE IN GRAPH");
                        break;
                  }
            }
      }
}