Readable Dijkstra's - Java - Pure template based
What is Dijkstra\'s Algorithm (we call it D.A here) and why do we care here ?\n\n1. D.A is an algorithm to find hte shortest distance from 1 ROOT NODE to ALL OT
**What is Dijkstra\'s Algorithm (we call it D.A here) and why do we care here ?**\n\n1. D.A is an algorithm to find hte shortest distance from 1 ROOT NODE to ALL OTHER ROOT NODES in a GRAPH. \n2. Think about finding the shortest distance from San Jose to San Francisco, Los Angeles and Fremont in a Graph of 4 Cities [San Jose, San Francisco, Los Angeles, Fremont] \n3. If we have the starting City given and the distance between some cities in a Connected Manner ( path from any city A to any city B exists in some manner ) we should be able to calculate the Shortest Distance. \n4. We can ALSO COLLECT THE CITIES in the shortest paths but we dont care currently\n\n**How is it related to this question?**\n\n1. We have a source network node ( San Jose )\n2. We have many destination nodes ( Other cities )\n3. We are calculating the shortest time to propagate info from source to ALL other nodes ( Shortest distance from San Jose to others and then MAX of the Shortest Distances or times taken gives the EVENTUAL TIME TAKEN to propagate the messages from ROOT NODE to the LAST NODE )\n\n**What do we do then ?**\n\n1. Have a set of visited nodes which is initially empty\n```visited = {}```\n2. Have a Graph built from the provided times array as : \n```\nu = times[i][0] //Source\nv = times[i][1] // Destination\nw = times[i][2] // Edge Weight - Distance - time -> Anything you wanna call it\n\nGraph  = [{u, [v, w]}, {u2, [v2, w2]}...)\n```\n3. Maintain a distance array that contains the distances of ALL nodes from the root K. This means distance[K] = 0\n```\nArrays.fill(distance, Integer.MAX_VALUE) // Initially infinite distance\ndistance[K] = 0; // Root to Root is 0\ndistance[0] = 0; //There is no node called 0 and we just set it to 0 to prevent calculations. \n//If you are starting you nodes with 0 itself, make sure you calculate all nodes n as distance[n - 1]. \n//We will start from 1. So, ignore distance[0];\n```\n4. Create min heap to prioritize based on least distance from ROOT\n```\nComparator.comparing(node -> node[1]) where it will be the distace\n```\n5. Now, offer to the heap the ROOT with distance to itself as 0\n```\nheap.offer(new int[]{K, 0});\n```\n6. Now, for every item in the heap, repeat the following : \n```\ncurrent_source = heap.poll();\ndistance_from_root_to_current_source = current_source[1]; // Based on values offered to heap\nif(not_visited_current_source) {\n\t//for all neighbors of current source \n\t//if neighbor not visited as well\n\t//distance[neighbor] = Math.min(distance[neighbor], distance_from_root_to_current_source + weight of edge from u to current neighbor\n\theap.offer(new int[]{current_neighbor, distance[neighbor] });\n}\n```\n7. Now, return the MAX value from distance array as it is the max time taken to send signal to the LAST NODE from the ROOT only if all nodes have been visited. Else return - 1\n\n**CODE BELOW**\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        if(N == 0 || K < 1 || K > N || times == null || times.length == 0) return 0;\n        \n        int[] distance = new int[N + 1];\n        int[] visited = new int[N + 1];\n        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparing(a -> a[1]));\n        Map<Integer, List<int[]>> graph = new HashMap<>();\n        \n        Arrays.fill(distance, Integer.MAX_VALUE);\n        distance[K] = 0;\n        distance[0] = 0;\n        \n        for(int i = 0; i < times.length; i++) {\n            List<int[]> neighbors = graph.getOrDefault(times[i][0], new LinkedList<>());\n            neighbors.add(new int[]{times[i][1], times[i][2]});\n            graph.put(times[i][0], neighbors);\n        }\n        \n        heap.offer(new int[]{K, 0});\n        \n        while(!heap.isEmpty()) {\n            int u = heap.peek()[0];\n            int distUFromRoot = heap.poll()[1];\n            if(visited[u] == 1) continue;\n            visited[u] = 1;\n            \n            if(graph.containsKey(u)) {\n                for(int[] neighbor : graph.get(u)) {\n                    int v = neighbor[0];\n                    int w = neighbor[1];\n                    if(visited[v] == 0) {\n                        int newDistanceVFromRoot = Math.min(distance[v], w + distUFromRoot);\n                        distance[v] = newDistanceVFromRoot;\n                        heap.offer(new int[]{v, newDistanceVFromRoot});\n                    }\n                }\n            }\n        }\n        \n        for(int i = 1; i <= N; i++) {\n            if(visited[i] == 0) return -1;\n        }\n        \n        return Arrays.stream(distance).max().getAsInt();\n    }\n}
[]