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.

negative-weight cycle

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)

 

[gravityforms id="5" description="false" titla="false" ajax="true"]