Detect a negative cycle in a Graph using Shortest Path Faster Algorithm | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool sfpa ( int V , int src , int Edges [ ] [ 3 ] , int M ) { vector < pair < int , int > > g [ V ] ; for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; int w = Edges [ i ] [ 2 ] ; g [ u ] . push_back ( { v , w } ) ; } vector < int > dist ( V , INT_MAX ) ; vector < bool > inQueue ( V , false ) ; vector < int > cnt ( V , 0 ) ; dist [ src ] = 0 ; queue < int > q ; q . push ( src ) ; inQueue [ src ] = true ; while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop ( ) ; inQueue [ u ] = false ; for ( pair < int , int > 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 . push ( v ) ; inQueue [ v ] = true ; cnt [ v ] ++ ; if ( cnt [ v ] >= V ) return true ; } } } } return false ; } int main ( ) { int N = 4 ; int src = 0 ; int M = 4 ; int Edges [ ] [ 3 ] = { { 0 , 1 , 1 } , { 1 , 2 , -1 } , { 2 , 3 , -1 } , { 3 , 0 , -1 } } ; if ( sfpa ( N , src , Edges , M ) == true ) cout << " Yes " << endl ; else cout << " No " << endl ; return 0 ; }