Java Simple Bellman-Ford Algorithm Solution - 2 Approaches with Explanation
1) This approach shows that we can use the times array given to us as number of edges and perform Bellman-Ford Algorithm to be able to also detect any negative 
1) This approach shows that we can use the times array given to us as number of edges and perform Bellman-Ford Algorithm to be able to also detect any negative cycles.\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        //create distance array and set them to MAX_VALUE except the starting node K to 0.\n        int[] dist = new int[N+1];\n        for(int i=1; i<dist.length; i++) {\n            dist[i] = Integer.MAX_VALUE;\n        }\n        dist[K] = 0;\n        \n        //try to relax all the edges\n        for(int i=1; i<N; i++) {\n            for(int[] edge: times) {\n                int source = edge[0];\n                int dest = edge[1];\n                int weight = edge[2];\n                if(dist[source]!=Integer.MAX_VALUE && dist[source] + weight < dist[dest]) {\n                    dist[dest] = dist[source] + weight;\n                }\n            }\n        }\n        \n        int max = Integer.MIN_VALUE;\n        // check to see if any of the distances are MAX_VALUE, this will\n        // show that the node was never relaxed so return -1\n        for(int i=0; i<dist.length; i++) {\n            if(dist[i]==Integer.MAX_VALUE){\n                return -1;\n            }\n            max = Math.max(max, dist[i]);\n        }\n        \n        return max;\n    }\n}\n```\n2. In this approach I created an Edge class to transform the times array into a graph of edges and then perform Bellman-Ford algorithm.\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        List<Edge> edges = new ArrayList<>();\n        \n        for(int i=0; i<times.length; i++) {\n            edges.add(new Edge(times[i][0], times[i][1], times[i][2]));\n        }\n        \n        int[] dist = new int[N+1];\n        for(int i=1; i<dist.length; i++) {\n            dist[i] = Integer.MAX_VALUE;\n        }\n        dist[K] = 0;\n        \n        for(int i=1; i<N; i++) {\n            for(Edge currEdge: edges) {\n                int source = currEdge.v;\n                int dest = currEdge.u;\n                int weight = currEdge.weight;\n                if(dist[source]!=Integer.MAX_VALUE && dist[source] + weight < dist[dest]) {\n                    dist[dest] = dist[source] + weight;\n                }\n            }\n        }\n        \n        int max = Integer.MIN_VALUE;\n        // check to see if any of the distance are MAX_VALUE, this will\n        // show that the node was never relaxed so return -1\n        for(int i=0; i<dist.length; i++) {\n            if(dist[i]==Integer.MAX_VALUE){\n                return -1;\n            }\n            max = Math.max(max, dist[i]);\n        }\n        \n        return max;\n    }\n    \n    class Edge {\n        int v;\n        int u;\n        int weight;\n        \n        Edge(int v, int u, int weight) {\n            this.v = v;\n            this.u = u;\n            this.weight = weight;\n        }\n        \n        public String toString() {\n            return " " + this.v + ", " + this.u + ", " + this.weight;\n        }\n    }\n}\n```
['Java']