Negative Weight Cycle

Problem Overview

Dijkstra cannot handle negative edges.

Intuition

Dijkstra cannot handle negative edges. Bellman-Ford can: if you relax every edge V-1 times and one more relax still improves a distance, some path got shorter by looping, which means a negative cycle. Starting every distance at 0 is the same as adding a virtual source with weight-0 edges into all vertices, so every component is checked in one run.

Algorithm

1Allocate dist[0..V-1] = 0.
2For up to V-1 rounds: for each edge (u, v, w), if dist[u] + w < dist[v], set dist[v] = dist[u] + w. If a round changes nothing, stop early.
3Scan every edge once more. If any edge can still relax, return true.
4Otherwise return false.

Example Walkthrough

Input: V = 3, edges = [[0,1,-1],[1,2,-2],[2,0,-3]]

1. Round 1 can pull distances down along the triangle.
2. After V-1 rounds, the same edges still improve a distance because the cycle weight is -6.
3. The final scan reports a negative cycle.

Output: true

Common Pitfalls

• A DFS that checks path weight from the DFS root is not the cycle weight and misses finished components.
• Initialize all dist to 0 (or use an explicit super-source). Starting from one vertex alone misses cycles in other components.
• You need the extra V-th pass (or equivalent check). Stopping after V-1 rounds only is not enough to detect the cycle.
• Early exit when a round is idle is optional but correct; it does not replace the final negative-cycle check if updates happened.

Negative Weight Cycle.java

Java

// Approach: Bellman-Ford with all distances starting at 0 (virtual super-
// source into every vertex). Relax every edge up to V-1 times, stopping early
// if a pass makes no change. One more successful relax means a negative cycle.
// Complexity: O(V * E) time and O(V) extra space.

class Solution {

    public boolean isNegativeWeightCycle(int V, int[][] edges) {
        int[] dist = new int[V];

        for (int i = 0; i < V - 1; i++) {
            boolean updated = false;

            for (int[] e : edges) {
                int u = e[0];
                int v = e[1];
                int w = e[2];

                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }

            if (!updated) {
                break;
            }
        }

        for (int[] e : edges) {
            if (dist[e[0]] + e[2] < dist[e[1]]) {
                return true;
            }
        }

        return false;
    }
}

Was this solution helpful?