Understanding Djikstra Algorithm for Beginners - Java Solution 9ms ✨
Approach\n- Find shortest path (minimum time) to reach all the nodes from node \'k\'\n- Find the max of all the minimum time\n- keep track of number of visited 
# Approach\n- Find shortest path (minimum time) to reach all the nodes from node \'k\'\n- Find the max of all the minimum time\n- keep track of number of visited nodes\n- if you ae able to reach all the nodes from \'k\' then minimum time to reach all the nodes is the maxmimum of all the reaching times.\n\nIf time taken to reach node `N1` and `N2` is `3` and` 4 `seconds respectively\nSo when will the sender recognize that both received the signal successfully?\n(ignoring round trip) **The answer is 4s**\nBy keeping this in mind lets move forward...\n### So how to do this ?\nBasically we\'ve to find shortest path (least delay path) from the starting node \'k\'\nAs we know DFS is not good for finding shortest path (dfs simply jumps to the first adjacent node and goes depth wise)\nWe\'ll do BFS here.. for good results.\n* First we\'ll have a queue \n* We\'ll also maintain a distance array containing final cost to reach each vertex from source vertex i.e for vertex \'v\' shortest distance from source to \'v\' will be `distance[v]` \n* We\'ll put the starting vertex.. since cost to reach starting vertex is zero.. mark the distance[start] = 0 \n* As we proceed the exploration on vertex start.. we\'ll visit all of its adjacent neighbors and add it to the queue\n**But** wait a minute before we add **we\'ll update the distance to reach those neighbors in there corresponding indices in distance array**.\nThis is called **relaxation**.\n\n### How we will do this ?\nI\'ll take an example...\nImagine this -\n```text\n        dis[u] = 0;\n        dis[v] =  INT_MAX; //initially we don\'t know the shortest path to reach there \n        dis[w] = INT_MAX; // this is called over-estimating the distance\n\n        u--------v----------w\n        0  (1)   Max  (2)  MAX\n\n        cost(u,v) = 1\n        cost(v,w) = 2\n\n        Start vertex 0\n        neighbor is vertex \'v\'\n        What is the min cost to reach v ?\n        do this..\n        (distance to reach u + cost to reach v)  If less than current distance to reach v i.e old distance[v]\n        then we update the distance of v\n\n        Since (o+1) < MAX\n        dis[v] = 1\n\n        Similarly to reach w from v\n        (dis[v] + cost(v, w)) < dist[w] or MAX\n        dis[w] = 1+2 = 3\n\n        distance array [0 1 3]\n                        u v w\n\t\t\t\t\t\t\n        This tells us that\n        If we start from u then..\n        Minimum cost to reach v is 1 and w is 3\n\n        We continue doing this.. and every time we select a vertex with minimum distance value. (unlike normal BFS there we directly remove the node from top of the queue)\n\n        This modified verision of BFS is also known as Dijkstra\'s Algorithm :)\n```\n# Complexity\n-   Time:\n    $$O(Vlog(E))$$, here V = vertices, E = number of edges\n-   Space:\n    $$O(V+E)$$\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int n, int k) {\n       // construct adj list\n       List[] adj = new List[n+1]; // given 1-indexed nodes\n       //O(times.length)\n       for(int[] time:times){\n           int u = time[0];\n           int v = time[1];\n           int t = time[2];\n           if(adj[u]==null){\n               adj[u] = new ArrayList<int[]>();\n           }\n           adj[u].add(new int[]{v,t}); // u->(v,t)\n       }\n       // we have to find shortest reaching time to all the other nodes from k\n       // and find max of all the reaching time\n       PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->Integer.compare(a[1],b[1]));\n       boolean[] vis = new boolean[n+1]; \n       \n       int[] reachTime = new int[n+1]; // store the optimal reach time to reach nodes\n       Arrays.fill(reachTime, Integer.MAX_VALUE); // infinity\n\n       int count = 0; // keep track of all the visited nodes\n       int max = 0; // max of all the shortest reaching time\n       \n       pq.add(new int[]{k,0});// cost to start node is zero\n       reachTime[k] = 0;\n\n       // use dijkstra algorithm\n       while(!pq.isEmpty()){\n           int[] node = pq.poll();\n           int u = node[0];\n           int reachTime_u = node[1];\n           if(vis[u]){\n               continue;\n           }\n           vis[u] = true;\n           count++; // count visited nodes\n           max = Math.max(max, reachTime_u); // update max\n           if(adj[u]!=null){\n               Iterator<int[]> it = adj[u].iterator();\n               while(it.hasNext()){\n                   int[] neighbor = it.next();\n                   int v = neighbor[0];\n                   int cost_uv = neighbor[1];\n                   // relaxation\n                   if(!vis[v] && (reachTime_u+cost_uv)<reachTime[v]){\n                    // if current estimation for reaching node \'v\' < previously estimated value\n                     reachTime[v] = reachTime_u+cost_uv;\n                     // dont mark as visited, there could be another path for reaching v \n                     // with lesses reach time\n                     pq.add(new int[]{v, reachTime[v]});\n                   }\n               }\n           }\n       }\n       return count==n?max:-1;\n    }\n}\n```\n\n
['Greedy', 'Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Shortest Path', 'Java']