Merge pull request TheAlgorithms#452 from PalAditya/master

Christian Bender · web-flow · commit ef6a188ff9bc · 2018-06-07T22:23:09.000+02:00
Added the implementation of the so far missing Bellman-Ford algorithm.
diff --git a/DataStructures/Graphs/BellmanFord.java b/DataStructures/Graphs/BellmanFord.java
@@ -0,0 +1,158 @@
+import java.util.*;
+class BellmanFord
+/*Implementation of Bellman ford to detect negative cycles. Graph accepts inputs in form of edges which have 
+start vertex, end vertes and weights. Vertices should be labelled with a number between 0 and total number of vertices-1,both inclusive*/
+{
+    int vertex,edge;
+    private Edge edges[];
+    private int index=0;
+    BellmanFord(int v,int e)
+    {
+        vertex=v;
+        edge=e;
+        edges=new Edge[e];
+    }
+    class Edge
+    {
+        int u,v;
+        int w;
+        /**
+        *@param u Source Vertex
+        * @param v End vertex
+        * @param c Weight
+        */
+        Edge(int a,int b,int c)
+        {
+            u=a;
+            v=b;
+            w=c;
+        }    
+    }
+    /**
+     * @param p[] Parent array which shows updates in edges
+     * @param  i Current vertex under consideration
+     */
+    void printPath(int p[],int i)
+    {
+        if(p[i]==-1)//Found the path back to parent
+            return;
+        printPath(p,p[i]);
+        System.out.print(i+" ");
+    }
+    public static void main(String args[])
+    {    
+        BellmanFord obj=new BellmanFord(0,0);//Dummy object to call nonstatic variables
+        obj.go();
+    }
+    public void go()//Interactive run for understanding the class first time. Assumes source vertex is 0 and shows distaance to all vertices
+    {
+        Scanner sc=new Scanner(System.in);//Grab scanner object for user input
+        int i,v,e,u,ve,w,j,neg=0;
+        System.out.println("Enter no. of vertices and edges please");
+        v=sc.nextInt();
+        e=sc.nextInt();
+        Edge arr[]=new Edge[e];//Array of edges 
+        System.out.println("Input edges");
+        for(i=0;i<e;i++)
+        {
+            u=sc.nextInt();
+            ve=sc.nextInt();
+            w=sc.nextInt();
+            arr[i]=new Edge(u,ve,w);
+        }
+        int dist[]=new int[v];//Distance array for holding the finalized shortest path distance between source and all vertices
+        int p[]=new int[v];//Parent array for holding the paths
+        for(i=0;i<v;i++)
+            dist[i]=Integer.MAX_VALUE;//Initializing distance values
+        dist[0]=0;
+        p[0]=-1;
+        for(i=0;i<v-1;i++)
+        {
+            for(j=0;j<e;j++)
+            {
+                if((int)dist[arr[j].u]!=Integer.MAX_VALUE&&dist[arr[j].v]>dist[arr[j].u]+arr[j].w)
+                {
+                    dist[arr[j].v]=dist[arr[j].u]+arr[j].w;//Update
+                    p[arr[j].v]=arr[j].u;
+                }
+            }
+        }
+        //Final cycle for negative checking
+        for(j=0;j<e;j++)
+        if((int)dist[arr[j].u]!=Integer.MAX_VALUE&&dist[arr[j].v]>dist[arr[j].u]+arr[j].w)
+        {
+            neg=1;
+            System.out.println("Negative cycle");
+            break;
+        }
+        if(neg==0)//Go ahead and show results of computaion
+        {
+            System.out.println("Distances are: ");
+            for(i=0;i<v;i++)
+            System.out.println(i+" "+dist[i]);
+            System.out.println("Path followed:");
+            for(i=0;i<v;i++)
+            { 
+                System.out.print("0 ");
+                printPath(p,i);
+                System.out.println();
+            }
+        }
+    }
+    /**
+     * @param source Starting vertex
+     * @param end Ending vertex
+     * @param Edge Array of edges 
+    */
+    public void show(int source,int end, Edge arr[])//Just shows results of computation, if graph is passed to it. The graph should
+    //be created by using addEdge() method and passed by calling getEdgeArray() method
+    {
+        int i,j,v=vertex,e=edge,neg=0;
+        double dist[]=new double[v];//Distance array for holding the finalized shortest path distance between source and all vertices
+        int p[]=new int[v];//Parent array for holding the paths
+        for(i=0;i<v;i++)
+            dist[i]=Integer.MAX_VALUE;//Initializing distance values
+        dist[source]=0;
+        p[source]=-1;
+        for(i=0;i<v-1;i++)
+        {
+            for(j=0;j<e;j++)
+            {
+                if((int)dist[arr[j].u]!=Integer.MAX_VALUE&&dist[arr[j].v]>dist[arr[j].u]+arr[j].w)
+                {
+                    dist[arr[j].v]=dist[arr[j].u]+arr[j].w;//Update
+                    p[arr[j].v]=arr[j].u;
+                }
+            }
+        }
+        //Final cycle for negative checking
+        for(j=0;j<e;j++)
+        if((int)dist[arr[j].u]!=Integer.MAX_VALUE&&dist[arr[j].v]>dist[arr[j].u]+arr[j].w)
+        {
+            neg=1;
+            System.out.println("Negative cycle");
+            break;
+        }
+        if(neg==0)//Go ahead and show results of computaion
+        {
+            System.out.println("Distance is: "+dist[end]);
+            System.out.println("Path followed:");
+            System.out.print(source+" ");
+            printPath(p,end);
+            System.out.println();
+        }
+    }
+    /**
+     *@param x Source Vertex
+     * @param y End vertex
+     * @param z Weight 
+    */
+    public void addEdge(int x,int y,int z)//Adds unidirectionl Edge
+    {
+        edges[index++]=new Edge(x,y,z);
+    }
+    public Edge[] getEdgeArray()
+    {
+       return edges;
+    }
+}
