[Java] | 🔥 100% | Dijkstra | Bellman Ford | SPFA | Floyd-Warshall
Dijkstra\n- TC: O(E + Elog(E))\n- SC: O(V+E)\n- 8 ms\n## Two different ways\njava []\nclass Solution {\n    record Node(int i, int t) {}\n    public int network
# Dijkstra\n- TC: O(E + Elog(E))\n- SC: O(V+E)\n- [8 ms](https://leetcode.com/problems/network-delay-time/submissions/879004707/)\n## Two different ways\n```java []\nclass Solution {\n    record Node(int i, int t) {}\n    public int networkDelayTime(int[][] times, int n, int k) {\n        // create graph\n        List<Node>[] g = new List[n];\n        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();\n        for (var t : times) g[t[0]-1].add(new Node(t[1]-1, t[2]));\n\n        int[] time = new int[n];\n        Queue<Integer> q = new PriorityQueue<>((u, v) -> time[u]-time[v]);\n        Arrays.fill(time, Integer.MAX_VALUE);\n        time[--k] = 0;\n        q.offer(k);\n\n        while (!q.isEmpty()) {\n            var cur = q.poll();\n            for (var next : g[cur]) {\n                int t2 = time[cur] + next.t;\n                if (t2 >= time[next.i]) continue;\n                time[next.i] = t2;\n                q.offer(next.i);\n            }\n        }\n\n        int res = time[0];\n        for (var t : time) if (t == Integer.MAX_VALUE) return -1; else if (t > res) res = t;\n        return res;\n    }\n}\n```\n```java []\nclass Solution {\n    record Node (int i, int t) {}\n    public int networkDelayTime(int[][] times, int n, int k) {\n        // create graph\n        List<Node>[] g = new List[n];\n        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();\n        for (var t : times) g[t[0]-1].add(new Node(t[1]-1, t[2]));\n\n        Queue<Node> q = new PriorityQueue<>((a, b) -> a.t - b.t);\n        q.offer(new Node(--k, 0));\n        int[] time = new int[n];\n        Arrays.fill(time, Integer.MAX_VALUE);\n        time[k] = 0;\n\n        while (!q.isEmpty()) {\n            var cur = q.poll();\n            for (var next : g[cur.i]) {\n                int t2 = cur.t + next.t;\n                if (t2 >= time[next.i]) continue;\n                time[next.i] = t2;\n                q.offer(new Node(next.i, t2));\n            }\n        }\n\n        int res = time[0];\n        for (var t : time) if (t == Integer.MAX_VALUE) return -1; else if (t > res) res = t;\n        return res;\n    }\n}\n```\n\n# Bellman Ford\n- TC: O(V*E) ==> n^3 (best O(E) => O(n^2))\n- SC: O(N)\n- [2ms with early termination 100%](https://leetcode.com/problems/network-delay-time/submissions/879012500/)\n- [13 ms without early termination](https://leetcode.com/problems/network-delay-time/submissions/879011956/)\n# Code\n```java\nclass Solution {\n    private final static int MAX = 1_000_000_000;\n    public int networkDelayTime(int[][] times, int n, int k) {\n        int[] time = new int[n+1];\n        Arrays.fill(time, MAX);\n        time[k] = time[0] = 0; // time[0] is garbage\n\n        for (int i = 1; i < n; i++) { // for n nodes, we iterate max n-1 times\n            boolean canRelax = false;\n            for (var e : times) if (time[e[0]] + e[2] < time[e[1]]) {\n                time[e[1]] = time[e[0]] + e[2];\n                canRelax = true;\n            }\n            if (!canRelax) break;\n        }\n\n        int res = time[1];\n        for (var t : time) if (t == MAX) return -1; else if (t > res) res = t;\n        return res;\n    }\n}\n```\n# SPFA\n- TC: Worst:\xA0O(V*E) same as\xA0Bellman-Ford. Avg:\xA0O(E)\n- SC: O(V)\n- [6ms](https://leetcode.com/problems/network-delay-time/submissions/879056523/)\n- [wiki SFPA](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm)\n# Code\n```java\nclass Solution {\n    record Node (int i, int t) {} \n    public int networkDelayTime(int[][] times, int n, int k) {\n        // create graph\n        List<Node>[] g = new List[n];\n        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();\n        for (var t : times) g[t[0]-1].add(new Node(t[1]-1, t[2]));\n\n        int[] time = new int[n];\n        Arrays.fill(time, Integer.MAX_VALUE);\n        time[--k] = 0;\n        boolean[] inQ = new boolean[n];\n        Queue<Integer> q = new ArrayDeque<>();\n        q.offer(k);\n\n        while (!q.isEmpty()) {\n            int cur = q.poll();\n            inQ[cur] = false;\n            for (var next : g[cur]) {\n                if (time[cur] + next.t < time[next.i]) {\n                    time[next.i] = time[cur] + next.t;\n                    if (!inQ[next.i]) {\n                        q.offer(next.i);\n                        inQ[next.i] = true;\n                    }\n                }\n            }\n        }\n\n        int res = time[0];\n        for (var t : time) if (t == Integer.MAX_VALUE) return -1; else if (t > res) res = t;\n        return res;\n    }\n}\n```\n# Floyd-Warshall\n- TC: O(V^3)\n- SC: O(V^2)\n- [10ms](https://leetcode.com/problems/network-delay-time/submissions/879057269/)\n\n# Code\n```java\nclass Solution {\n    private final static int MAX = 1_000_000_000; // for convenience\n    public int networkDelayTime(int[][] times, int n, int k) {\n        int[][] time = new int[n][n]; // we dont use 0\n        for (var t : time) Arrays.fill(t, MAX);\n        for (int i = 0; i < n; i++) time[i][i] = 0;\n        for (var t : times) time[t[0]-1][t[1]-1] = t[2]; // fill in the init matrix\n\n         // m as middle, intermediate\n        for (int m = 0; m < n; m++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)\n            if (time[i][m] + time[m][j] < time[i][j]) time[i][j] = time[i][m] + time[m][j];\n\n        int res = time[--k][0];\n        for (var t : time[k]) if (t == MAX) return -1; else if (t > res) res = t;\n        return res;\n    }\n}\n```
['Dynamic Programming', 'Java']