Print negative weight cycle in a Directed Graph | C ++ program for the above approach ; Structure to represent a weighted edge in graph ; Structure to represent a directed and weighted graph ; V -> Number of vertices , E -> Number of edges ; Graph is represented as an array of edges ; Creates a new graph with V vertices and E edges ; Function runs Bellman - Ford algorithm and prints negative cycle ( if present ) ; Initialize distances from src to all other vertices as INFINITE and all parent as - 1 ; Relax all edges | V | - 1 times . ; Check for negative - weight cycles ; Store one of the vertex of the negative weight cycle ; To store the cycle vertex ; Reverse cycle [ ] ; Printing the negative cycle ; Driver Code ; Number of vertices in graph ; Number of edges in graph ; Given Graph ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Edge { int src , dest , weight ; } ; struct Graph { int V , E ; struct Edge * edge ; } ; struct Graph * createGraph ( int V , int E ) { struct Graph * graph = new Graph ; graph -> V = V ; graph -> E = E ; graph -> edge = new Edge [ graph -> E ] ; return graph ; } void NegCycleBellmanFord ( struct Graph * graph , int src ) { int V = graph -> V ; int E = graph -> E ; int dist [ V ] ; int parent [ V ] ; for ( int i = 0 ; i < V ; i ++ ) { dist [ i ] = INT_MAX ; parent [ i ] = -1 ; } dist [ src ] = 0 ; for ( int i = 1 ; i <= V - 1 ; i ++ ) { for ( int j = 0 ; j < E ; j ++ ) { int u = graph -> edge [ j ] . src ; int v = graph -> edge [ j ] . dest ; int weight = graph -> edge [ j ] . weight ; if ( dist [ u ] != INT_MAX && dist [ u ] + weight < dist [ v ] ) { dist [ v ] = dist [ u ] + weight ; parent [ v ] = u ; } } } int C = -1 ; for ( int i = 0 ; i < E ; i ++ ) { int u = graph -> edge [ i ] . src ; int v = graph -> edge [ i ] . dest ; int weight = graph -> edge [ i ] . weight ; if ( dist [ u ] != INT_MAX && dist [ u ] + weight < dist [ v ] ) { C = v ; break ; } } if ( C != -1 ) { for ( int i = 0 ; i < V ; i ++ ) C = parent [ C ] ; vector < int > cycle ; for ( int v = C ; ; v = parent [ v ] ) { cycle . push_back ( v ) ; if ( v == C && cycle . size ( ) > 1 ) break ; } reverse ( cycle . begin ( ) , cycle . end ( ) ) ; for ( int v : cycle ) cout << v << ' ▁ ' ; cout << endl ; } else cout << " - 1" << endl ; } int main ( ) { int V = 5 ; int E = 5 ; struct Graph * graph = createGraph ( V , E ) ; graph -> edge [ 0 ] . src = 0 ; graph -> edge [ 0 ] . dest = 1 ; graph -> edge [ 0 ] . weight = 1 ; graph -> edge [ 1 ] . src = 1 ; graph -> edge [ 1 ] . dest = 2 ; graph -> edge [ 1 ] . weight = 2 ; graph -> edge [ 2 ] . src = 2 ; graph -> edge [ 2 ] . dest = 3 ; graph -> edge [ 2 ] . weight = 3 ; graph -> edge [ 3 ] . src = 3 ; graph -> edge [ 3 ] . dest = 4 ; graph -> edge [ 3 ] . weight = -3 ; graph -> edge [ 4 ] . src = 4 ; graph -> edge [ 4 ] . dest = 1 ; graph -> edge [ 4 ] . weight = -3 ; NegCycleBellmanFord ( graph , 0 ) ; return 0 ; }