Detect a negative cycle in a Graph using Shortest Path Faster Algorithm | Javascript 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 ; Number of vertices ; Given source node src ; Number of Edges ; Given Edges with weight ; If cycle is present
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } function sfpa ( V , src , Edges , M ) { var g = Array . from ( Array ( V ) , ( ) => Array ( ) ) ; for ( var i = 0 ; i < M ; i ++ ) { var u = Edges [ i ] [ 0 ] ; var v = Edges [ i ] [ 1 ] ; var w = Edges [ i ] [ 2 ] ; g [ u ] . push ( new pair ( v , w ) ) ; } var dist = Array ( V ) ; for ( var i = 0 ; i < V ; i ++ ) dist [ i ] = 1000000000 ; var inQueue = Array ( V ) . fill ( false ) ; var cnt = Array ( V ) . fill ( 0 ) ; dist [ src ] = 0 ; var q = [ ] ; q . push ( src ) ; inQueue [ src ] = true ; while ( q . length != 0 ) { var u = q [ 0 ] ; q . shift ( ) ; inQueue [ u ] = false ; for ( var x of g [ u ] ) { var v = x . first ; var 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 ; } var N = 4 ; var src = 0 ; var M = 4 ; var Edges = [ [ 0 , 1 , 1 ] , [ 1 , 2 , - 1 ] , [ 2 , 3 , - 1 ] , [ 3 , 0 , - 1 ] ] ; if ( sfpa ( N , src , Edges , M ) == true ) document . write ( " " + " " ) ; else document . write ( " " + " " ) ;