Dijkstra | Bellman Ford | Floyd Warshall
Time Complexity\nDijkstra - V + ElogE\nBellman Ford - VE\nFloyd Warshall - V^3\n\nDijkstra\n\n\nclass Solution {\n    public int networkDelayTime(int[][] times,
**Time Complexity**\nDijkstra - V + ElogE\nBellman Ford - VE\nFloyd Warshall - V^3\n\n**Dijkstra**\n\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        List<int[]>[] adj = new ArrayList[N];\n        for (int i = 0; i < N; i++) {\n            adj[i] = new ArrayList<>();\n        }\n\n        for (int[] t : times) {\n            adj[t[0] - 1].add(new int[]{t[1] - 1, t[2]});\n        }\n\n        int[] dist = new int[N];\n        Arrays.fill(dist, -1);\n\n        dist[K - 1] = 0;\n        Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));\n        minHeap.offer(new int[]{K - 1, 0});\n\n        while (minHeap.size() > 0) {\n            int curr = minHeap.peek()[0];\n            minHeap.poll();\n            for (int[] pair : adj[curr]) {\n                int next = pair[0];\n                int weight = pair[1];\n                int d = dist[curr] + weight;\n                if (dist[next] == -1 || dist[next] > d) {\n                    dist[next] = d;\n                    minHeap.offer(new int[]{next, dist[next]});\n                }\n            }\n        }\n\n        int maxwait = 0;\n        for (int i = 0; i < N; i++) {\n            if(dist[i] == -1) \n                return -1;\n            maxwait = Math.max(maxwait, dist[i]);\n        }\n        return maxwait;\n    }\n}\n```\n\n************\n\n**Bellman Ford**\n\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int[] dist = new int[N + 1];\n        Arrays.fill(dist, Integer.MAX_VALUE);\n        \n        dist[K] = 0;\n        for(int i = 1; i < N; i++) {\n            for(int[] e : times) {\n                int u = e[0], v = e[1], w = e[2];\n                if(dist[u] != Integer.MAX_VALUE && dist[v] > dist[u] + w)\n                    dist[v] = dist[u] + w;\n            }\n        }\n        \n        int maxwait = 0;\n        for (int i = 1; i <= N; i++)\n            maxwait = Math.max(maxwait, dist[i]);\n        return maxwait == Integer.MAX_VALUE ? -1 : maxwait;\n    }\n}\n```\n\n\n**Bellman Short Code**\n\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int[] dist = new int[N];\n        Arrays.fill(dist, Integer.MAX_VALUE);\n        dist[K - 1] = 0;\n        for(int i = 1; i < N; i++)\n            for(int[] e : times)\n                if(dist[e[0] - 1] != Integer.MAX_VALUE && dist[e[1] - 1] > dist[e[0] - 1] + e[2])\n                    dist[e[1] - 1] = dist[e[0] - 1] + e[2];\n        \n        int maxwait = Arrays.stream(dist).max().getAsInt();\n        return maxwait == Integer.MAX_VALUE ? -1 : maxwait;\n    }\n}\n```\n\n************\n\n**Floyd Warshall **\n\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int MAX = 1000000;\n        int[][] dist = new int[N][N];\n        for(int i = 0; i < N; i++)\n            Arrays.fill(dist[i], MAX);\n        for(int i = 0; i < N; i++)\n            dist[i][i] = 0;\n        for(int[] e : times)\n            dist[e[0] - 1][e[1] - 1] = e[2];\n        \n        for(int k = 0; k < N; k++)\n            for(int i = 0; i < N; i++)\n                for(int j = 0; j < N; j++) \n                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);\n        \n        int maxwait = 0;\n        for(int i = 0; i < N; i++)\n            maxwait = Math.max(maxwait, dist[K - 1][i]);\n        return maxwait == MAX ? -1 : maxwait;\n    }\n}\n```
[]