Simple Dijkstra's Solution in Java along with great intuition using Priority Queue
Intuition\nUsing the simple generic Dijkstras algorithm with little tweak to solve the problem.\nData Structures to be used here is:\n1. Array: to store distanc
# Intuition\nUsing the simple generic Dijkstras algorithm with little tweak to solve the problem.\nData Structures to be used here is:\n1. **Array**: to store distance from source\n*In the code*: d - to store distance of each vertex from source node.\nInitially make it infinity for all the vertex except source.\nFor source set it to 0 since from source we can reach the source in 0.\n\n2. **HashMap**: to store the graph in the form of adjacency list(adjacent vertex connected from a vertex) for fast traversal\n*In the code*: map - convert the given times[i] to this form for fast traversal\nKey - vertex\nValue - List of integer array which contains the adjacent vertex and their distances to that particular vertex in the format source,target and the weight (times[i] = (ui, vi, wi)).\n\n3. **Priority Queue** to get the shortest distance vertex from source in O(1) time\nIt contains an integer array which contains the vertex and the distance from source of that vertex.\nPriority is determined based on distance from the source.\nSyntax in java: PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);\n\n4. **Set**: To keep track of the processed nodes\nIntially empty.\nfill it one by one by the nodes that are getting processed.\n\n![2.jpeg](https://assets.leetcode.com/users/images/6c5f0577-99d5-4382-9d94-15bd1b3be881_1668006448.7860146.jpeg)\n![1.jpeg](https://assets.leetcode.com/users/images/073925a0-fae2-4b98-ba2b-6d8822110fd8_1668006437.620692.jpeg)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Pick a vertex everytime starting from the source.\n2. update the distance of its adjacent vertices from source which is updating the d array which stores the distance of the source.\n3. As soon as you relax the adjacent edges add it to the priority queue which will pick the vertex with minimum distance from source for the next iteration \nA vertex is processed when its adjacent vertices are relaxed.\n\nRepeat:\n    - Pick a node everytime based on shortest distance from source\n    - relax adjacent vertices\nuntil all vertices are processed.\n\nRealxing the Vertices:\n    Picked a vertex u;\n    Relaxing vertex v which is adjacent to vertex u using the logic:\n         if(d[v]>d[u]+distance)\n                        d[v]=d[u]+distance;\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(V+E(Log(V)))\n    V vertices in the graph each need to be traversed. Logn is the insertion time for each vertices in the heap (priority queue) here n is V;\nif a vertex is added twice in priority queue the maximum number of time it can be added is the number of edges. hence ElogV.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int n, int source) {\n\n        HashMap<Integer,List<int[]>> map = new HashMap();\n\n        for(int[] time:times)\n        {\n            if(!map.containsKey(time[0]))\n            {\n                List<int[]> l = new LinkedList();\n                l.add(time);\n                map.put(time[0],l);\n            }\n            else\n            {\n                List<int[]> lk =map.get(time[0]);\n                lk.add(time);\n                map.put(time[0],lk);\n            }\n        }\n\n\n        // intialize the distance array and fill it as infinity\n        int[] d = new int[n+1];\n        Arrays.fill(d,10000);\n        d[source]=0;\n\n//            priority based on distance in pq int[]{node , distance_from_source}\n//            priority based on distance\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);\n        pq.add(new int[]{source,d[source]});\n\n        HashSet<Integer> processed = new HashSet();\n\n\n        while(pq.size()!=0)\n        {\n            int[] current =pq.poll();\n            int u =current[0];\n//            int distance = current[1];\n\n            if(processed.contains(u)) continue;\n\n            processed.add(u);\n\n// update all the distance of adjacent nodes from the selected node\n// relaxing step\n            if(map.containsKey(u))\n                for(int[] nodes:map.get(u))\n                {\n                    int v =nodes[1];\n                    int distance=nodes[2];\n                    if(d[v]>d[u]+distance)\n                        d[v]=d[u]+distance;\n                    pq.add(new int[]{v,d[v]});\n                }\n        }\n\n<!-- return the maximum time taken  -->\n        int max=0;\n        for(int i=1;i<d.length;i++)\n        {\n            if(i==source) continue;\n            else\n                max=Math.max(max,d[i]);\n        }\n\n<!-- if we are unable to reach a node return -1 -->\n        if(processed.size()!=n) return -1;\n        else return max;\n    }\n}\n```
['Greedy', 'Graph', 'Heap (Priority Queue)', 'Java']