Dijkstra_algo

class Solution
{
    class Pair{ // instead of pair, named it edge
        int node, distance;
        Pair(int n,int d){
            node = n;
            distance = d;
        }
    }
    public  int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
    {
        int[]dist=new int[V];
        Arrays.fill(dist,(int)1e9);
        PriorityQueue<Pair>pq=new PriorityQueue<>((a,b)->a.distance-b.distance); // min heap

        dist[S]=0;
        pq.add(new Pair(S,0));

        while(!pq.isEmpty()){
            Pair top=pq.remove();
            int currNode=top.node;
            int currDist=top.distance;
            if(dist[currNode]<currDist)continue; // i think this line will improve tc as if currnode is already explored it's nbr with better distance then if we consider larger distance then it is un-necessary and it is time consuming although all condition will failed but we can avoid it by adding this line.

            // explore all nbr of this currNode 
            for(ArrayList<Integer>nbr:adj.get(currNode)){
                int v=nbr.get(0);
                int w=nbr.get(1);

                // to reach v we take w + currDist

                if(w+currDist < dist[v]){ // must be less than, not less than equal to, if true means to reach 'v', we found better path ie through 'u'
                    dist[v]=w+currDist;
                    pq.add(new Pair(v,w+currDist));
                }
            }
        }
        return dist;
    }
}