Problem Statement

Given a weighted directed graph with n nodes and m edges. Nodes are labeled from 0 to n-1, the task is to check if it contains a negative weight cycle or not.Note: edges[i] is defined as u, v and weight.

Example 1:

Input:n = 3, edges = {{0,1,-1},{1,2,-2},
{2,0,-3}}
Output:1
Explanation:The graph contains negative weight
cycle as 0->1->2->0 with weight -1,-2,-3,-1.

Example 2:

Input:n = 3, edges = {{0,1,-1},{1,2,-2},
{2,0,3}}
Output:0
Explanation:The graph does not contain any
negative weight cycle.

Problem Link

Negative weight cycle | Practice | GeeksforGeeks

Reference Videos

https://www.youtube.com/watch?v=FrLWd1tJ_Wc&list=PLEJXowNB4kPzByLnnFYNSCoqtFz0VKLk5&index=23&ab_channel=TECHDOSETECHDOSE

https://www.youtube.com/watch?v=24HziTZ8_xo&list=PLEJXowNB4kPzByLnnFYNSCoqtFz0VKLk5&index=24&ab_channel=TECHDOSETECHDOSE

Code

class Solution {
public:
	int isNegativeWeightCycle(int n, vector<vector<int>>edges){
	    int e = edges.size();
	    bool updated = false;
	    vector<int> weight(n,INT_MAX);
	    weight[0] = 0;
	    
	    for(int i=0;i<n-1;i++) // n-1 relaxations
	    {
	        updated = false;
	        for(auto edge:edges) // iterate for each edge
	        {
	            int u = edge[0];
	            int v = edge[1];
	            int wt = edge[2];
	            
	            if(weight[u]!=INT_MAX and weight[v]>weight[u]+wt)
	            {
	                weight[v]=weight[u]+wt;
	                updated = true; // atleast one edge got updated in ith relaxation
	            }
	        }
	        if(!updated)// if none of the edges got updated in ith relaxation
	        break;
	        
	    }
	    
	    for(auto edge:edges)
	    {
	       int u = edge[0];
	       int v = edge[1];
	       int wt = edge[2];
	            
	       if(weight[u]!=INT_MAX and weight[v]>weight[u]+wt)
	           return 1;
	            
	    }
	        
	   
	  return 0;
	    
	}
};