# How to detect negative edge weight cycle in a graph ?

Given a directed weighted graph with possibly negative edge weights, how to detect the presence of a negative edge weight cycle in the graph ?

## What is a negative edge weight cycle ?

The weight of a cycle in a graph is the sum of all the edge weights in the cycle for the graph. For example, in the graph given below there are multiple cycles :

1. 0-2-3-1-0 : The weight of this cycle is -2 + 2 + (-1) + 4 = 3
2. 1-2-3-1: The weight of this cycle is (-3) + 2 + (-1) = -2

Since the weight of the 2nd cycle is negative, hence it is a negative edge weight cycle in the graph.

## How to detect negative edge weight cycle in a graph ?

To detect negative edge weight cycle, we will be using Floyd Warshall algorithm, which is a dynamic programming based approach. It is also used to solve the shortest path problem.

The idea behind Floyd Warshall algorithm is to iterate over all the edges exactly n times sequentially and prepare a matrix which stores the distance b/w any two nodes. At the end of the algorithm, the matrix will contain the shortest distance b/w any two pair of nodes.

See the diagram below for more details.

Let’s say there is a negative edge weight cycle b/w any two nodes `(i,i)`, the value stored at `matrix[i][i]` will be negative. Therefore, at the completion of the Floyd Warshall algorithm, we can just check the value at `matrix[i][i]` for all the values of `i`. If even one of them is negative, it means that there is a negative edge weight cycle in the graph.

## Detecting negative edge weight cycle implementation

```#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the adjMatrix
#define N 4

// define infinity as maximum value of the integer
#define INF INT_MAX

// Function to run Floyd-Warshell algorithm
{
// cost[] stores shortest-path information
int cost[N][N];

// initialize cost[] matrix
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
// Initially cost would be same as weight of the edge
}
}

// Run Floyd-Warshell
for (int k = 0; k < N; k++)
{
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
// If vertex k is on the shortest path from v to u,
// then update the value of cost[v][u]

if (cost[v][k] != INF && cost[k][u] != INF
&& cost[v][k] + cost[k][u] < cost[v][u])
{
cost[v][u] = cost[v][k] + cost[k][u];
}
}

// If diagonal elements become negative, the
// graph contains a negative weight cycle
if (cost[v][v] < 0)
{
cout << "Negative Weight Cycle Found!!";
return;
}
}
}

cout << "No Negative Weight Cycle Found";
}

int main()
{
// given adjacency representation of matrix
{
{ 0,   INF, -2,  INF },
{ 4,   0,   -3,  INF },
{ INF, INF, 0,   2 },
{ INF, -1,  INF, 0 }
};

// Run Floyd Warshell algorithm

return 0;
}```

```# define infinity as maximum value of the integer
INF = float('inf')

# Function to run Floyd-Warshell algorithm

# cost stores shortest-path information
# Initially cost would be same as weight of the edge
cost = [[adjMatrix[v][u] for u in range(N)] for v in range(N)]

# Run Floyd-Warshell
for k in range(N):
for v in range(N):
for u in range(N):
# If vertex k is on the shortest path from v to u,
# then update the value of cost[v][u]
if (cost[v][k] != INF and cost[k][u] != INF
and cost[v][k] + cost[k][u] < cost[v][u]):
cost[v][u] = cost[v][k] + cost[k][u]

# If diagonal elements become negative, the
# graph contains a negative weight cycle
if cost[v][v] < 0:
print("Negative Weight Cycle Found")
return

print("No Negative Weight Cycle Found")

if __name__ == '__main__':

# given adjacency representation of matrix
[0, INF, -2, INF],
[4, 0, -3, INF],
[INF, INF, 0, 2],
[INF, -1, INF, 0]
]

# Number of vertices in the adjMatrix
N = 4

# Run Floyd Warshell algorithm