Q44 Bellman ford | GFG ( Smaller code)
Thu Jun 22 2023 10:19:35 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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;
}
content_copyCOPY
Comments