shortestPathdirectedweightedGraph.java

import java.util.*;
import java.io.*;
import java.lang.*;

//Pair Class
class Pair{

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

class Main {

    void topologicalSortUtil(int node, Boolean visited[], Stack stack, ArrayList<ArrayList<Pair>> adj){
        visited[node]=true;
        for(Pair it: adj.get(node)){
            if(visited[it.getV()]==false){
                topologicalSortUtil(it.getV(), visited, stack, adj);
            }
        }
        stack.add(node);
    }

    void shortestPath(int s, ArrayList<ArrayList<Pair>> adj, int N)
    {
        Stack stack=new Stack();
        int dist[]=new int[N];

        Boolean visited[]=new Boolean[N];
        for(int i=0; i<N; i++)
            visited[i]=false;

        for(int i=0; i<N; i++)
            if(visited[i]==false)
                topologicalSortUtil(i, visited, stack, adj);
        
        for(int i=0;i<N;i++)
            dist[i]=Integer.MAX_VALUE;
        dist[i]=0;

        while(stack.empty()==false){
            int node=(int)stack.pop();

            //if node has been reached previously
            if(dist[node]!= Integer.MAX_VALUE)
            {
                for(Pair it: adj.get(node)){
                    if(dist[node]+it.getWeight() < dist[it.getV()]){
                        dist[it.getV()]=dist[node]+it.getWeight();
                    }
                  }
                }
            }

            for(int i=0; i<N; i++){
                if(dist[i]==Integer.MAX_VALUE)
                    System.out.println("INF"); 
                else
                    System.out.println(dist[i] + " ");
                
            }
        }
       
    public static void main(String[] args) {
    int n=6;
    ArrayList<ArrayList<Pair>> adj= new ArrayList<ArrayList<Pair>>();

    for(int i=0; i<n; i++)
       adj.add(new ArrayList<Pair>());

       adj.get(0).add(new Pair(1,2));
       adj.get(1).add(new Pair(4,1));
       adj.get(2).add(new Pair(2,3));
       adj.get(3).add(new Pair(3,6));
       adj.get(4).add(new Pair(2,2));
       adj.get(5).add(new Pair(5,4));
       adj.get(6).add(new Pair(3,1));

       Main obj=new Main();
       obj.shortestPath(0,adj,n);

   }
}