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 :

- 0-2-3-1-0 : The weight of this cycle is -2 + 2 + (-1) + 4 = 3
- 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 void FloydWarshell(int adjMatrix[][N]) { // 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 cost[v][u] = adjMatrix[v][u]; } } // 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 int adjMatrix[N][N] = { { 0, INF, -2, INF }, { 4, 0, -3, INF }, { INF, INF, 0, 2 }, { INF, -1, INF, 0 } }; // Run Floyd Warshell algorithm FloydWarshell(adjMatrix); return 0; }

# define infinity as maximum value of the integer INF = float('inf') # Function to run Floyd-Warshell algorithm def FloydWarshell(adjMatrix): # 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 adjMatrix = [ [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 FloydWarshell(adjMatrix)