Q24 Distance from the Source (Bellman-Ford Algorithm) | Practice | GeeksforGeeks

//{ Driver Code Starts
import java.util.*;
import java.io.*;
import java.lang.*;

class DriverClass {
    public static void main(String args[]) throws IOException {

        BufferedReader read =
            new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while (t-- > 0) {
            String str[] = read.readLine().trim().split(" ");
            int V = Integer.parseInt(str[0]);
            int E = Integer.parseInt(str[1]);

            ArrayList<ArrayList<Integer>> edges = new ArrayList<>();

            int i = 0;
            while (i++ < E) {
                String S[] = read.readLine().trim().split(" ");
                int u = Integer.parseInt(S[0]);
                int v = Integer.parseInt(S[1]);
                int w = Integer.parseInt(S[2]);
                ArrayList<Integer> t1 = new ArrayList<>();
                t1.add(u);
                t1.add(v);
                t1.add(w);
                edges.add(t1);
            }

            int S = Integer.parseInt(read.readLine());

            Solution ob = new Solution();

            int[] ptr = ob.bellman_ford(V, edges, S);

            for (i = 0; i < ptr.length; i++) System.out.print(ptr[i] + " ");
            System.out.println();
        }
    }
}
// } Driver Code Ends


// User function Template for Java

/*
*   edges: vector of vectors which represents the graph
*   S: source vertex to start traversing graph with
*   V: number of vertices
*/
class Solution {
    static int[] bellman_ford(int vtx, ArrayList<ArrayList<Integer>> edges, int S) {
        /* Q24 of graph playlist , bellman Ford algo 
        */
        
        //adding all the edges once in a arraylist (already done here)
        
        //iterating v-1 times
        int path[] = new int[vtx];
        Arrays.fill(path , Integer.MAX_VALUE);
        path[S] = 0;    //source to source is 0
        
        for(int i = 0 ;i < vtx-1 ; i++){
            
            //iterating over every edge
            for(int j = 0 ; j < edges.size() ; j++){
                //taking out edge
                int u = edges.get(j).get(0);
                int v = edges.get(j).get(1);
                int wt = edges.get(j).get(2);
                
                if(path[u] == Integer.MAX_VALUE){
                    continue;
                }
                
                if(path[u] + wt < path[v])
                path[v] = path[u] + wt;
            }
        }
        
        /* if negative weight cycle exists in the graph , path on one node will 
        update if we do another iteration of bellmanford (Vth iteration)
        */
        //iterating over every edge for Vth time to check for negative weight cycle
            for(int j = 0 ; j < edges.size() ; j++){
                //taking out edge
                int u = edges.get(j).get(0);
                int v = edges.get(j).get(1);
                int wt = edges.get(j).get(2);
                
                if(path[u] == Integer.MAX_VALUE){
                    continue;
                }
                
                //if true then that means , cycle exists
                if(path[u] + wt < path[v]){
                    return new int[]{-1};
                }
                
            }
            
        
         for(int i = 0 ;i < vtx; i++){
             if(path[i] == Integer.MAX_VALUE)
             path[i] = 100000000;
         }
        return path;
    }
}