Bellmanford.java

//srishti1302
import java.util.*;

// A class to represent a connected, directed and weighted graph
class bellman {
        // A class to represent a weighted edge in graph
        class Edge {
                int src, dest, weight;
                Edge()
                {
                        src = dest = weight = 0;
                }
        }

        int V, E;
        Edge edge[];

        // Creates a graph with V vertices and E edges
        bellman(int v, int e)
        {
                V = v;
                E = e;
                edge = new Edge[e];
                for (int i = 0; i < e; ++i)
                        edge[i] = new Edge();
        }

        // The main function that finds shortest distances from src
        // to all other vertices using Bellman-Ford algorithm. The
        // function also detects negative weight cycle
        void BellmanFord(bellman graph, int src)
        {
                int V = graph.V, E = graph.E;
                int dist[] = new int[V];

                // Step 1: Initialize distances from src to all other
                // vertices as INFINITE
                for (int i = 0; i < V; ++i)
                        dist[i] = Integer.MAX_VALUE;
                dist[src] = 0;

                // Step 2: Relax all edges |V| - 1 times. A simple
                // shortest path from src to any other vertex can
                // have at-most |V| - 1 edges
                for (int i = 1; i < V; ++i) {
                        for (int j = 0; j < E; ++j) {
                                int u = graph.edge[j].src;
                                int v = graph.edge[j].dest;
                                int weight = graph.edge[j].weight;
                                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
                                        dist[v] = dist[u] + weight;
                        }
                }

                // Step 3: check for negative-weight cycles. The above
                // step guarantees shortest distances if graph doesn't
                // contain negative weight cycle. If we get a shorter
                // path, then there is a cycle.
                for (int j = 0; j < E; ++j) {
                        int u = graph.edge[j].src;
                        int v = graph.edge[j].dest;
                        int weight = graph.edge[j].weight;
                        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                                System.out.println("Graph contains negative weight cycle");
                                return;
                        }
                }
                printArr(dist, V);
        }

        // A utility function used to print the solution
        void printArr(int dist[], int V)
        {
                System.out.println("Vertex Distance from Source");
                for (int i = 0; i < V; ++i)
                        System.out.println(i + "\t\t" + dist[i]);
        }

        // Driver method to test above function
        public static void main(String[] args)
        {       Scanner s=new Scanner(System.in);
        System.out.println("Enter number of vertices n edges");
                int V = s.nextInt(); // Number of vertices in graph
                int E = s.nextInt(); // Number of edges in graph

                bellman graph = new bellman(V, E);
                for(int i=0;i<E;i++)
                {       System.out.println("Enter sirce destinaion n weight for edge"+ i);
                        graph.edge[i].src=s.nextInt();
                        graph.edge[i].dest=s.nextInt();
                        graph.edge[i].weight=s.nextInt();
                }

                graph.BellmanFord(graph, 0);
                s.close();
        }
}