Detecting negative cycle using Floyd Warshall | Number of vertices in the graph ; Define Infinite as a large enough value . This value will be used for vertices not connected to each other ; Returns true if graph has negative weight cycle else false . ; dist [ ] [ ] will be the output matrix that will finally have the shortest distances between every pair of vertices ; Initialize the solution matrix same as input graph matrix . Or we can say the initial values of shortest distances are based on shortest paths considering no intermediate vertex . ; Add all vertices one by one to the set of intermediate vertices . -- -> Before start of a iteration , we have shortest distances between all pairs of vertices such that the shortest distances consider only the vertices in set { 0 , 1 , 2 , . . k - 1 } as intermediate vertices . -- -- > After the end of a iteration , vertex no . k is added to the set of intermediate vertices and the set becomes { 0 , 1 , 2 , . . k } ; Pick all vertices as source one by one ; Pick all vertices as destination for the above picked source ; If vertex k is on the shortest path from i to j , then update the value of dist [ i ] [ j ] ; If distance of any vertex from itself becomes negative , then there is a negative weight cycle . ; Let us create the following weighted graph 1 ( 0 ) -- -- -- -- -- -> ( 1 ) / | \ | | | - 1 | | - 1 | \ | / ( 3 ) < -- -- -- -- -- - ( 2 ) - 1
V = 4 NEW_LINE INF = 99999 NEW_LINE def negCyclefloydWarshall ( graph ) : NEW_LINE INDENT dist = [ [ 0 for i in range ( V + 1 ) ] for j in range ( V + 1 ) ] NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT dist [ i ] [ j ] = graph [ i ] [ j ] NEW_LINE DEDENT DEDENT for k in range ( V ) : NEW_LINE INDENT for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT if ( dist [ i ] [ k ] + dist [ k ] [ j ] < dist [ i ] [ j ] ) : NEW_LINE INDENT dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( V ) : NEW_LINE INDENT if ( dist [ i ] [ i ] < 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT graph = [ [ 0 , 1 , INF , INF ] , [ INF , 0 , - 1 , INF ] , [ INF , INF , 0 , - 1 ] , [ - 1 , INF , INF , 0 ] ] NEW_LINE if ( negCyclefloydWarshall ( graph ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT