Detecting negative cycle using Floyd Warshall | C ++ Program to check if there is a negative weight cycle using Floyd Warshall Algorithm ; 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 verex from itself becomes negative , then there is a negative weight cycle . ; driver program ; Let us create the following weighted graph 1 ( 0 ) -- -- -- -- -- -> ( 1 ) / | \ | | | - 1 | | - 1 | \ | / ( 3 ) < -- -- -- -- -- - ( 2 ) - 1
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define V  4 NEW_LINE void printSolution ( int dist [ ] [ V ] ) ; #define INF  99999 NEW_LINE bool negCyclefloydWarshall ( int graph [ ] [ V ] ) { int dist [ V ] [ V ] , i , j , k ; for ( i = 0 ; i < V ; i ++ ) for ( j = 0 ; j < V ; j ++ ) dist [ i ] [ j ] = graph [ i ] [ j ] ; for ( k = 0 ; k < V ; k ++ ) { for ( i = 0 ; i < V ; i ++ ) { for ( j = 0 ; j < V ; j ++ ) { if ( dist [ i ] [ k ] + dist [ k ] [ j ] < dist [ i ] [ j ] ) dist [ i ] [ j ] = dist [ i ] [ k ] + dist [ k ] [ j ] ; } } } for ( int i = 0 ; i < V ; i ++ ) if ( dist [ i ] [ i ] < 0 ) return true ; return false ; } int main ( ) { int graph [ V ] [ V ] = { { 0 , 1 , INF , INF } , { INF , 0 , -1 , INF } , { INF , INF , 0 , -1 } , { -1 , INF , INF , 0 } } ; if ( negCyclefloydWarshall ( graph ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }