Print negative weight cycle in a Directed Graph | Java 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
import java . util . ArrayList ; import java . util . Collections ; class GFG { static class Edge { int src , dest , weight ; } static class Graph { int V , E ; Edge [ ] edge ; } static Graph createGraph ( int V , int E ) { Graph graph = new Graph ( ) ; graph . V = V ; graph . E = E ; graph . edge = new Edge [ graph . E ] ; for ( int i = 0 ; i < graph . E ; i ++ ) { graph . edge [ i ] = new Edge ( ) ; } return graph ; } static void NegCycleBellmanFord ( Graph graph , int src ) { int V = graph . V ; int E = graph . E ; int [ ] dist = new int [ V ] ; int [ ] parent = new int [ V ] ; for ( int i = 0 ; i < V ; i ++ ) { dist [ i ] = 1000000 ; 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 ] != 1000000 && 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 ] != 1000000 && dist [ u ] + weight < dist [ v ] ) { C = v ; break ; } } if ( C != - 1 ) { for ( int i = 0 ; i < V ; i ++ ) C = parent [ C ] ; ArrayList < Integer > cycle = new ArrayList < > ( ) ; for ( int v = C ; ; v = parent [ v ] ) { cycle . add ( v ) ; if ( v == C && cycle . size ( ) > 1 ) break ; } Collections . reverse ( cycle ) ; for ( int v : cycle ) System . out . print ( v + " ▁ " ) ; System . out . println ( ) ; } else System . out . println ( - 1 ) ; } public static void main ( String [ ] args ) { int V = 5 ; int E = 5 ; 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 ) ; } }