1. Introduction
A negative weight cycle is a cycle in a directed weighted graph where the sum of all edge weights is negative.
For example:
1 → 2 → 3 → 1
If the weights are:
1 → 2 = -6
2 → 3 = 5
3 → 1 = -2
Then the total weight is:
-6 + 5 + (-2) = -3
Since the total is negative, this graph contains a negative weight cycle.
The best-known algorithm to detect a negative weight cycle is the Bellman-Ford algorithm.
2. Problem Statement
We are given:
[u, v, w]
where:
u = source vertex
v = destination vertex
w = edge weight
We need to return:
true
if the graph contains a negative weight cycle.
Otherwise, return:
false
3. Why Bellman-Ford?
There are several shortest-path algorithms, but Bellman-Ford is useful here because it can handle:
Unlike Dijkstra's algorithm, Bellman-Ford can work with negative edge weights.
The important property is:
If we can still improve a distance after V - 1 relaxations, then a negative weight cycle exists.
4. What is Relaxation?
Relaxation means checking whether going through one edge gives us a shorter distance.
Suppose we have:
u → v
with weight w.
We check:
dist[v] > dist[u] + w
If this condition is true, we update:
dist[v] = dist[u] + w
For example:
dist[u] = 5
w = -3
dist[v] = 10
Then:
dist[u] + w
= 5 + (-3)
= 2
Since:
2 < 10
we update:
dist[v] = 2
5. Java Solution
class Solution {
public boolean isNegativeWeightCycle(int V, int[][] edges) {
long[] dist = new long[V];
// Relax all edges V times
for (int i = 0; i < V; i++) {
boolean updated = false;
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
updated = true;
// Relaxation on Vth iteration
// means negative weight cycle exists
if (i == V - 1) {
return true;
}
}
}
// No update means no negative cycle
if (!updated) {
break;
}
}
return false;
}
}
6. Code Explanation
Step 1: Create the distance array
long[] dist = new long[V];
This array stores the current minimum distance for every vertex.
In Java, long[] is used instead of int[] because edge weights can be negative and repeated additions can potentially exceed the safe range of int.
Initially:
dist[0] = 0
dist[1] = 0
dist[2] = 0
...
7. Why Are All Distances Initialized to 0?
Normally, Bellman-Ford starts from a single source vertex.
But this problem asks:
Does the graph contain a negative cycle anywhere?
The graph may be disconnected.
For example:
0 → 1
and separately:
2 → 3 → 2
If we start only from vertex 0, we might never reach the cycle involving 2 and 3.
Initializing every distance to 0 is equivalent to adding a virtual source connected to every vertex with an edge of weight 0.
Therefore, we can detect a negative cycle in any component.
8. Outer Loop
for (int i = 0; i < V; i++) {
We relax all edges repeatedly.
Why V times?
For a graph containing V vertices, a shortest simple path can contain at most:
V - 1 edges
Therefore, V - 1 iterations are normally enough.
If we can still relax an edge during the Vth iteration, something unusual is happening.
That "something" is a negative cycle.
9. Loop Through Every Edge
for (int[] edge : edges) {
Each edge looks like:
[u, v, w]
So we extract the values:
int u = edge[0];
int v = edge[1];
int w = edge[2];
For example:
[1, 2, -6]
means:
u = 1
v = 2
w = -6
Therefore:
1 → 2
has weight:
-6
10. Relax the Edge
The most important line is:
if (dist[v] > dist[u] + w) {
This checks whether we can reach v with a smaller distance through u.
If yes:
dist[v] = dist[u] + w;
We update the distance.
11. Detecting the Negative Cycle
We keep track of whether any update happened:
boolean updated = false;
When an edge is relaxed:
updated = true;
Then:
if (i == V - 1) {
return true;
}
This is the key condition.
If an update happens during the Vth iteration, it means the distances are still decreasing after V - 1 rounds.
That can only happen because of a negative weight cycle.
12. Why Does a Negative Cycle Cause Continuous Updates?
Consider:
1 → 2 → 3 → 1
with weights:
1 → 2 = -6
2 → 3 = 5
3 → 1 = -2
Total:
-6 + 5 - 2 = -3
Every time we go around the cycle, the total distance decreases by 3.
For example:
First cycle: distance decreases by 3
Second cycle: distance decreases by 3
Third cycle: distance decreases by 3
...
Therefore, the algorithm keeps finding smaller distances.
This is why an update can still happen on the Vth iteration.
13. Early Termination
We have:
if (!updated) {
break;
}
Suppose we complete an iteration and none of the distances changed.
That means no edge can provide a shorter distance.
Therefore, there is no need to continue.
This improves performance for graphs that don't require all V iterations.
14. Example 1
Input:
V = 4
edges = [
[0, 3, 6],
[1, 0, 4],
[1, 2, 6],
[3, 1, 2]
]
There is a cycle:
1 → 0 → 3 → 1
Weights:
1 → 0 = 4
0 → 3 = 6
3 → 1 = 2
Total:
4 + 6 + 2 = 12
The total is positive.
Therefore:
No negative weight cycle
Output:
false
15. Example 2
Input:
V = 4
edges = [
[1, 0, 4],
[3, 1, -2],
[1, 2, -6],
[2, 3, 5]
]
Cycle:
1 → 2 → 3 → 1
Weights:
1 → 2 = -6
2 → 3 = 5
3 → 1 = -2
Total:
-6 + 5 - 2 = -3
Since:
-3 < 0
there is a negative weight cycle.
Output:
true
16. Why Not Use Dijkstra?
Dijkstra's algorithm assumes that edge weights are non-negative.
For example:
A → B = 4
B → C = -10
Negative edges can cause Dijkstra's greedy approach to produce incorrect results.
Bellman-Ford is specifically designed to handle negative edge weights.
Therefore:
Negative edges → Bellman-Ford
Negative cycle detection → Bellman-Ford
17. Time Complexity
There are at most:
V
iterations.
During every iteration, we check:
E
edges.
Therefore:
Time Complexity = O(V × E)
Given:
V ≤ 1000
E ≤ 100000
this matches the expected complexity.
18. Space Complexity
We only maintain:
long[] dist = new long[V];
Therefore:
Space Complexity = O(V)
We don't need an adjacency list for this implementation.
19. Complete Logic in Simple Terms
The entire algorithm can be remembered like this:
1. Create distance array.
2. Initialize every distance to 0.
3. Repeat V times:
Check every edge.
Try to reduce the destination distance.
4. If an update happens during the Vth iteration:
Negative cycle exists.
5. Otherwise:
No negative cycle.
The most important condition is:
if (dist[v] > dist[u] + w)
and the most important detection is:
if (i == V - 1)
return true;
20. Final Code
class Solution {
public boolean isNegativeWeightCycle(int V, int[][] edges) {
long[] dist = new long[V];
for (int i = 0; i < V; i++) {
boolean updated = false;
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
updated = true;
if (i == V - 1) {
return true;
}
}
}
if (!updated) {
break;
}
}
return false;
}
}
Key Interview Point
If the interviewer asks:
"How do you detect a negative weight cycle using Bellman-Ford?"
The short answer is:
Relax all edges V - 1 times. If any edge can still be relaxed on the Vth iteration, the graph contains a negative weight cycle.
For a graph that may be disconnected, initialize all distances to 0 (or use a virtual source connected to every vertex with weight 0) so that cycles in every component are considered.