Detect a negative cycle in a Graph using Shortest Path Faster Algorithm | Python3 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 sys NEW_LINE def sfpa ( V , src , Edges , M ) : NEW_LINE INDENT g = [ [ ] for i in range ( V ) ] NEW_LINE for i in range ( M ) : NEW_LINE INDENT u = Edges [ i ] [ 0 ] NEW_LINE v = Edges [ i ] [ 1 ] NEW_LINE w = Edges [ i ] [ 2 ] NEW_LINE g [ u ] . append ( [ v , w ] ) NEW_LINE DEDENT dist = [ sys . maxsize for i in range ( V ) ] NEW_LINE inQueue = [ False for i in range ( V ) ] NEW_LINE cnt = [ 0 for i in range ( V ) ] NEW_LINE dist [ src ] = 0 NEW_LINE q = [ ] NEW_LINE q . append ( src ) NEW_LINE inQueue [ src ] = True NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT u = q [ 0 ] NEW_LINE q . remove ( q [ 0 ] ) NEW_LINE inQueue [ u ] = False NEW_LINE for x in g [ u ] : NEW_LINE INDENT v = x [ 0 ] NEW_LINE cost = x [ 1 ] NEW_LINE if ( dist [ v ] > dist [ u ] + cost ) : NEW_LINE INDENT dist [ v ] = dist [ u ] + cost NEW_LINE if ( inQueue [ v ] == False ) : NEW_LINE INDENT q . append ( v ) NEW_LINE inQueue [ v ] = True NEW_LINE cnt [ v ] += 1 NEW_LINE if ( cnt [ v ] >= V ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE src = 0 NEW_LINE M = 4 NEW_LINE Edges = [ [ 0 , 1 , 1 ] , [ 1 , 2 , - 1 ] , [ 2 , 3 , - 1 ] , [ 3 , 0 , - 1 ] ] NEW_LINE if ( sfpa ( N , src , Edges , M ) == True ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT