Detect a negative cycle in a Graph using Shortest Path Faster Algorithm | Java program for the above approach ; Stores the adjacency list of the given graph ; Create Adjacency List ; Stores the distance of all reachable vertex from source ; Check if vertex is present in queue or not ; Counts the relaxation for each vertex ; Distance from src to src is 0 ; Create a queue ; Push source in the queue ; Mark source as visited ; Front vertex of Queue ; Relaxing all edges of vertex from the Queue ; Update the dist [ v ] to minimum distance ; If vertex v is in Queue ; Negative cycle ; No cycle found ; Driver Code ; Number of vertices ; Given source node src ; Number of Edges ; Given Edges with weight ; If cycle is present
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static boolean sfpa ( int V , int src , int Edges [ ] [ ] , int M ) { Vector < pair > [ ] g = new Vector [ V ] ; for ( int i = 0 ; i < V ; i ++ ) { g [ i ] = new Vector < pair > ( ) ; } for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; int w = Edges [ i ] [ 2 ] ; g [ u ] . add ( new pair ( v , w ) ) ; } int [ ] dist = new int [ V ] ; Arrays . fill ( dist , Integer . MAX_VALUE ) ; boolean [ ] inQueue = new boolean [ V ] ; int [ ] cnt = new int [ V ] ; dist [ src ] = 0 ; Queue < Integer > q = new LinkedList < > ( ) ; q . add ( src ) ; inQueue [ src ] = true ; while ( ! q . isEmpty ( ) ) { int u = q . peek ( ) ; q . remove ( ) ; inQueue [ u ] = false ; for ( pair x : g [ u ] ) { int v = x . first ; int cost = x . second ; if ( dist [ v ] > dist [ u ] + cost ) { dist [ v ] = dist [ u ] + cost ; if ( ! inQueue [ v ] ) { q . add ( v ) ; inQueue [ v ] = true ; cnt [ v ] ++ ; if ( cnt [ v ] >= V ) return true ; } } } } return false ; } public static void main ( String [ ] args ) { int N = 4 ; int src = 0 ; int M = 4 ; int Edges [ ] [ ] = { { 0 , 1 , 1 } , { 1 , 2 , - 1 } , { 2 , 3 , - 1 } , { 3 , 0 , - 1 } } ; if ( sfpa ( N , src , Edges , M ) == true ) System . out . print ( " Yes " + "NEW_LINE"); else System . out . print ( " No " + "NEW_LINE"); } }