class Solution { static int[] bellman_ford(int vtx, ArrayList<ArrayList<Integer>> edges, int s) { path = new int[vtx]; return bellman(vtx , edges , s) == true ? path : new int[]{-1}; } static int path[]; public static boolean bellman(int vtx, ArrayList<ArrayList<Integer>> edges, int s){ Arrays.fill(path , 100000000); path[s] = 0; boolean negative_wtcyle = false; //we need only v-1 iteration but we check till v iteration to check for negative //wt cycle for(int i = 0 ;i < vtx ; i++){ for(ArrayList<Integer> edge : edges){ int u = edge.get(0), v = edge.get(1) , wt = edge.get(2); if(path[u] == Integer.MAX_VALUE) continue; if(path[u] + wt < path[v]){ path[v] = path[u]+wt; //if at vth iteration distance get updated its negative wt cycle if(i == vtx-1) negative_wtcyle = true; } } } return negative_wtcyle == false ? true : false; }