[3 Ways to Solve Java]Floyd Warshall && Dijkstra && Bellman Ford
It\'s kind of brute force. Floyd Warshall:\n\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int[][] M = new int[N + 
It\'s kind of brute force. Floyd Warshall:\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int[][] M = new int[N + 1][N + 1];\n        for(int[] row : M){\n            Arrays.fill(row, 10000);\n        }\n        for(int[] t : times){\n            int v1 = t[0];\n            int v2 = t[1];\n            int cost = t[2];\n            M[v1][v2] = cost;\n        }\n        for(int m = 1; m <= N; m ++){\n        \tfor(int i = 1; i <= N; i ++){\n        \t\tfor(int j = 1; j <= N; j ++){\n        \t\t\tif(M[i][m] + M[m][j] < M[i][j]){\n        \t\t\t\tM[i][j] = M[i][m] + M[m][j];\n        \t\t\t}\n        \t\t}\n        \t}\n        }\n        int max = Integer.MIN_VALUE;\n        for(int i = 1; i <= N; i ++){\n            if(i == K){\n                continue;\n            }\n            if(M[K][i] == 10000){\n                return -1;\n            }\n            max = Math.max(max, M[K][i]);\n        }\n        return max == 10000 ? -1 : max;\n    }\n}\n```\n\nDijkstra:\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[2] - b[2]));\n        int[][] graph = new int[N + 1][N + 1];\n        for(int[] row : graph){\n            Arrays.fill(row, -1);\n        }\n        for(int[] t : times){\n            graph[t[0]][t[1]] = t[2];\n        }\n        for(int i = 1; i <= N; i ++){\n            if(graph[K][i] != -1){\n                heap.offer(new int[]{K, i, graph[K][i]});\n            }\n        }\n        int[] minCost = new int[N + 1];\n        Arrays.fill(minCost, -1);\n        while(!heap.isEmpty()){\n            int[] cur = heap.poll();\n            int u = cur[0];\n            int v = cur[1];\n            int cost = cur[2];\n            if(minCost[v] == -1){\n                minCost[v] = cost;\n            }\n            for(int i = 1; i <= N; i ++){\n                if(graph[v][i] != -1 && minCost[i] == -1){\n                    heap.offer(new int[]{K, i, cost + graph[v][i]});\n                }\n            }\n        }\n        int max = Integer.MIN_VALUE;\n        for(int i = 1; i <= N; i ++){\n            if(i == K){\n                continue;\n            }\n            if(minCost[i] == -1){\n                return -1;\n            }\n            max = Math.max(minCost[i], max);\n        }\n        return max == Integer.MIN_VALUE ? -1 : max;\n    }\n}\n```\nHowever, Dijkstra takes around 150ms. Floyd takes around 80ms, faster than Dijkstra. \nFloyd time complexity should be O(V^3), while Dijkstra should be O(E*logE).(Correct me if im wrong)\nIdk what happend behind the scene, could anyone tell me why? \nE can be upto V^2, even in worst case, E*logE = V^2 * logV^2 = 2V^2logV.\nV^3 is still greater 2V^2logV.\n\nBellman Ford:\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int[] dis = new int[N + 1];\n        Arrays.fill(dis, Integer.MAX_VALUE);\n        dis[K] = 0;\n        for(int i = 1; i <= N; i ++){\n            if(i == K){\n                continue;\n            }\n            for(int[] edge : times){\n                int u = edge[0];\n                int v = edge[1];\n                int cost = edge[2];\n                if(dis[u] != Integer.MAX_VALUE && dis[u] + cost < dis[v]){\n                    dis[v] = dis[u] + cost;\n                }\n            }\n        }\n        int max = Integer.MIN_VALUE;\n        for(int i = 1; i <= N; i ++){\n            if(i == K){\n                continue;\n            }\n            max = Math.max(max, dis[i]);\n        }\n        return max == Integer.MAX_VALUE ? -1 : max;\n    }\n}\n```\nBellmanFord is faster, around 50 ms.
[]