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:

Code
1 → 2 → 3 → 1

If the weights are:

Code
1 → 2 = -6
2 → 3 = 5
3 → 1 = -2

Then the total weight is:

Code
-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:

Code
[u, v, w]

where:

We need to return:

Code
true

if the graph contains a negative weight cycle.

Otherwise, return:

Code
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:

Code
u → v

with weight w.

We check:

Code
dist[v] > dist[u] + w

If this condition is true, we update:

Code
dist[v] = dist[u] + w

For example:

Code
dist[u] = 5
w = -3
dist[v] = 10

Then:

Code
dist[u] + w
= 5 + (-3)
= 2

Since:

Code
2 < 10

we update:

Code
dist[v] = 2

5. Java Solution

Java
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

Java
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:

Code
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:

Code
0 → 1

and separately:

Code
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

Java
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:

Code
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

Java
for (int[] edge : edges) {

Each edge looks like:

Code
[u, v, w]

So we extract the values:

Java
int u = edge[0];
int v = edge[1];
int w = edge[2];

For example:

Code
[1, 2, -6]

means:

Code
u = 1
v = 2
w = -6

Therefore:

Code
1 → 2

has weight:

Code
-6

10. Relax the Edge

The most important line is:

Java
if (dist[v] > dist[u] + w) {

This checks whether we can reach v with a smaller distance through u.

If yes:

Java
dist[v] = dist[u] + w;

We update the distance.

11. Detecting the Negative Cycle

We keep track of whether any update happened:

Java
boolean updated = false;

When an edge is relaxed:

Java
updated = true;

Then:

Java
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:

Code
1 → 2 → 3 → 1

with weights:

Code
1 → 2 = -6
2 → 3 = 5
3 → 1 = -2

Total:

Code
-6 + 5 - 2 = -3

Every time we go around the cycle, the total distance decreases by 3.

For example:

Code
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:

Java
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:

Code
V = 4

edges = [
    [0, 3, 6],
    [1, 0, 4],
    [1, 2, 6],
    [3, 1, 2]
]

There is a cycle:

Code
1 → 0 → 3 → 1

Weights:

Code
1 → 0 = 4
0 → 3 = 6
3 → 1 = 2

Total:

Code
4 + 6 + 2 = 12

The total is positive.

Therefore:

Code
No negative weight cycle

Output:

Code
false

15. Example 2

Input:

Code
V = 4

edges = [
    [1, 0, 4],
    [3, 1, -2],
    [1, 2, -6],
    [2, 3, 5]
]

Cycle:

Code
1 → 2 → 3 → 1

Weights:

Code
1 → 2 = -6
2 → 3 = 5
3 → 1 = -2

Total:

Code
-6 + 5 - 2 = -3

Since:

Code
-3 < 0

there is a negative weight cycle.

Output:

Code
true

16. Why Not Use Dijkstra?

Dijkstra's algorithm assumes that edge weights are non-negative.

For example:

Code
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:

Code
Negative edges → Bellman-Ford
Negative cycle detection → Bellman-Ford

17. Time Complexity

There are at most:

Code
V

iterations.

During every iteration, we check:

Code
E

edges.

Therefore:

Code
Time Complexity = O(V × E)

Given:

Code
V ≤ 1000
E ≤ 100000

this matches the expected complexity.

18. Space Complexity

We only maintain:

Java
long[] dist = new long[V];

Therefore:

Code
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:

Code
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:

Java
if (dist[v] > dist[u] + w)

and the most important detection is:

Java
if (i == V - 1)
    return true;

20. Final Code

Java
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.