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)
