Dikjstra.java

import java.util.*;

public class Dikjstra {
    public static void main(String args[]) {

        Graphh g = new Graphh(8);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 1);
        g.addEdge(3,2,0);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 4, 1);
        g.addEdge(4, 5, 2);
        g.addEdge(4,1,3);
        g.addEdge(3,0,9);
        g.addEdge(2,0,5);
        g.addEdge(5,0,1);
        g.addEdge(1,6,1);
        g.addEdge(6,7,1);
        g.addEdge(7,0,1);
        g.addEdge(1,0,10);
        int s = 1;
        System.out.println("Following are shortest distances " +
                "from source " + s);
        Graphh.shortestPath(s);
    }

    // First - defining a graph
    // Comes the int Vertices, then how are we going to store vertices and that is adjecency list
    // an array of Linkedlist, each index of that array contains the linked list of the elements which are adjascent to that index vertex
    // the linkedlist will contain Nodes the nodes will contain the value of this vertice and the weight of the edge with starting value
    // the index of the array and ending value this vertices
    // Make a new Queue - PriorityQueue. - It will contain Nodes containing 2 elements {value,distance_from_source_uptil_now}
    // and PriorityQueue will be sorted according with the distance_from_source_till_now


    static class Graphh{
        static private int V;
        static private LinkedList<AdjListNode> adj[];
        Graphh(int v)
        {
            V=v;
            adj = new LinkedList[V];
            for (int i=0; i<v; ++i)
                adj[i] = new LinkedList<AdjListNode>();
        }
        void addEdge(int u, int v, int weight)
        {
            AdjListNode node = new AdjListNode(v,weight);
            adj[u].add(node);// Add v to u's list
        }

        public static Comparator<Node> distComparator = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.dist-o2.dist;
            }
        };

        static void shortestPath(int s){
            int[] distances = new int[8];
            boolean[] visited = new boolean[8];
            int[] parent = new int[8];

            for(int i=0;i<8;i++){
                distances[i]=Integer.MAX_VALUE;
            }

            Node n = new Node(s,0);
            Queue<Node> q = new PriorityQueue<>(distComparator);
            q.add(n);
            distances[s]=0;
            parent[0]=Integer.MIN_VALUE;


            while (!q.isEmpty()){
                Node node = q.poll();
                visited[node.data]=true;
                int temp = node.data;
                for(AdjListNode a:adj[temp]){

                    if(!visited[a.getV()]){

                    if(distances[a.getV()]>a.getWeight()+distances[temp]){
                        distances[a.getV()]=a.getWeight()+distances[temp];
                        parent[a.getV()]=temp;
                    }

                    Node n1 = new Node(a.getV(),distances[a.getV()]);
                    q.add(n1);
                    }
                }
            }


            // The reason why Dikjstra works is, we see all the adjascent elemens of the source and priorize the next elements
            // wrt the next nearest element and then also we see the next element considering that nearest elements

            for(int i=0;i<8;i++) {
                System.out.println(i + "-" + distances[i]);
            }

            for(int i=0;i<8;i++) {
                System.out.println(i+" = "+parent[i]);
            }

            for(int i=0;i<8;i++) {
                System.out.println("Path from "+s+" to "+i);
                int x = i;
                List<Integer> st = new ArrayList<>();
                while (x!=s){
                    st.add(x);
                    x=parent[x];
                }
                st.add(x);
                Collections.reverse(st);
                System.out.println(st);
            }

        }
    }

    static class AdjListNode
    {
        private int v;
        private int weight;
        AdjListNode(int _v, int _w) { v = _v;  weight = _w; }
        int getV() { return v; }
        int getWeight()  { return weight; }
    }

    static class Node{
        int data;
        int dist;

        Node(int data,int dist){
            this.data=data;
            this.dist=dist;
        }
        int getData(){return data;}
        int getDist(){return dist;}
    }
}