package com.interview.graph;

import java.util.HashMap;
import java.util.Map;

/**
 * Date 11/05/2015
 * @author Tushar Roy
 *
 * Write program for Bellman Ford algorithm to find single source shortest path in directed graph.
 * Bellman ford works with negative edges as well unlike Dijksra's algorithm. If there is negative
 * weight cycle it detects it.
 *
 * Time complexity - O(EV)
 * Space complexity - O(V)
 *
 * References
 * https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
 * http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
 */

public class BellmanFordShortestPath {

    private static int INFINITY = 10000000;

    class CycleException extends RuntimeException {
    }
    
    public Map<Vertex<Integer>, Integer> getShortestPath(Graph<Integer> graph,
            Vertex<Integer> startVertex) {
        Map<Vertex<Integer>, Integer> distance = new HashMap<>();
        Map<Vertex<Integer>, Vertex<Integer>> predecessor = new HashMap<>();

        for(Vertex<Integer> v : graph.getAllVertex()) {
            distance.put(v, INFINITY);
            predecessor.put(v, null);
        }

        distance.put(startVertex, 0);

        int totalVertices = graph.getAllVertex().size() - 1;

        //relax edges repeatedly
        for (int i = 0; i < totalVertices ; i++) {
            for (Edge<Integer> edge : graph.getAllEdges()) {
                Vertex<Integer> u = edge.getVertex1();
                Vertex<Integer> v = edge.getVertex2();
                //if we get better distance to v via u then use this distance
                //and set u as predecessor of v.
                if (distance.get(u) + edge.getWeight() < distance.get(v)) {
                    distance.put(v, distance.get(u) + edge.getWeight());
                    predecessor.put(v, u);
                }
            }
        }

        //relax all edges again. If we still get better distance it means
        //there is negative weight cycle in the graph. Throw exception in that
        //case
        for (Edge<Integer> edge : graph.getAllEdges()) {
            Vertex<Integer> u = edge.getVertex1();
            Vertex<Integer> v = edge.getVertex2();
            if (distance.get(u) + edge.getWeight() < distance.get(v)) {
                throw new CycleException();
            }
        }
        return distance;
    }

    public static void main(String args[]){
        
        Graph<Integer> graph = new Graph<Integer>(false);
        graph.addEdge(1, 4,4);
        graph.addEdge(1, 2,3);
        graph.addEdge(2, 4,2);
        graph.addEdge(2, 3,3);
        graph.addEdge(3, 4,1);
        graph.addEdge(5, 4,1);
        graph.addEdge(3, 5,2);
        graph.addEdge(3, 6,1);
        graph.addEdge(5, 6,2);
        
        BellmanFordShortestPath shortestPath = new BellmanFordShortestPath();
        Vertex<Integer> startVertex = graph.getAllVertex().iterator().next();
        Map<Vertex<Integer>,Integer> distance = shortestPath.getShortestPath(graph, startVertex);
        System.out.println(distance);
    }

}

@@ -615,16 +615,173 @@
 Path %7B%0A%0A
+    //some random big number is treated as infinity. I m not taking INTEGER_MAX as infinity because%0A    //doing any addition on that causes integer overflow%0A
     priv
@@ -827,16 +827,30 @@
   class 
+NegativeWeight
 CycleExc
@@ -998,28 +998,29 @@
 x%3CInteger%3E s
-tart
+ource
 Vertex) %7B%0A  
@@ -1013,24 +1013,25 @@
 ceVertex) %7B%0A
+%0A
         Map%3C
@@ -1131,26 +1131,21 @@
 eger%3E%3E p
+a
 re
-decessor
+nt
  = new H
@@ -1153,24 +1153,88 @@
 shMap%3C%3E();%0A%0A
+        //set distance of every vertex to be infinity initially%0A
         for(
@@ -1325,34 +1325,29 @@
            p
+a
 re
-decessor
+nt
 .put(v, null
@@ -1352,32 +1352,80 @@
 ll);%0A        %7D%0A%0A
+        //set distance of source vertex to be 0%0A
         distance
@@ -1430,20 +1430,21 @@
 ce.put(s
-tart
+ource
 Vertex, 
@@ -1460,29 +1460,17 @@
     int 
-totalVertices
+V
  = graph
@@ -1495,12 +1495,8 @@
 ze()
- - 1
 ;%0A%0A 
@@ -1526,16 +1526,28 @@
 peatedly
+ V - 1 times
 %0A       
@@ -1571,21 +1571,13 @@
 i %3C 
-totalVertices
+V - 1
  ; i
@@ -1745,32 +1745,65 @@
 e.getVertex2();%0A
+                //relax the edge%0A
                 
@@ -1896,26 +1896,21 @@
 t u as p
+a
 re
-decessor
+nt
  of v.%0A 
@@ -2082,18 +2082,13 @@
    p
+a
 re
-decessor
+nt
 .put
@@ -2183,28 +2183,28 @@
 e still get 
-bett
+less
 er distance 
@@ -2563,16 +2563,30 @@
 row new 
+NegativeWeight
 CycleExc
@@ -2745,23 +2745,16 @@
 w Graph%3C
-Integer
 %3E(false)
@@ -2781,14 +2781,15 @@
 dge(
-1, 4,4
+0, 3, 8
 );%0A 
@@ -2813,14 +2813,15 @@
 dge(
-1, 2,3
+0, 1, 4
 );%0A 
@@ -2845,14 +2845,15 @@
 dge(
-2, 4,2
+0, 2, 5
 );%0A 
@@ -2877,13 +2877,15 @@
 dge(
+1, 
 2, 
-3,
+-
 3);%0A
@@ -2910,45 +2910,15 @@
 dge(
-3
+2
 , 4,
-1);%0A        graph.addEdge(5, 4,1
+ 4
 );%0A 
@@ -2941,18 +2941,19 @@
 Edge(3, 
-5,
+4, 
 2);%0A    
@@ -2974,56 +2974,18 @@
 dge(
-3, 6,1);%0A        graph.addEdge(5, 6,2);%0A        
+4, 3, 1);%0A
 %0A   

update in Bellman ford