class Solution { public int networkDelayTime(int[][] times, int n, int k) { /*Q26 graph playlist ,bellman ford we are not using any temp array here as we dont need result of every iteration we just need minimum path from source to every dest and we will return max of all min-paths as our answer */ int path[] = new int[n]; Arrays.fill(path , Integer.MAX_VALUE); path[k-1] = 0; int ans = -1; for(int i = 0 ;i < n-1 ; i++){ for(int time[] : times){ int u = time[0] , v = time[1] , wt = time[2]; if(path[u-1] == Integer.MAX_VALUE) continue; //turned into 0 based indexing path[v-1] = Math.min(path[v-1] ,path[u-1] + wt ); } } //finding maximum of all min paths for(int i = 0 ;i < n ; i++) ans = Math.max(ans , path[i]); //if any min path is still max_Value we return -1 return ans == Integer.MAX_VALUE ? -1 : ans; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter