Similar Problems
Similar Problems not available
How to detect negative edge weight cycle in a graph ? - Leetcode Solution
LeetCode: How to detect negative edge weight cycle in a graph ? Leetcode Solution
Difficulty: Unknown
Topics: graphs
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.
How to detect negative edge weight cycle in a graph ? Solution Code
1