Detect a Negative Cycle

1. Define the problem

You are given n nodes labeled 0 to n - 1, a list of directed edges edges where edges_i = [u, v, w], and a source node src. Return true if a negative-weight cycle is reachable from src, or false otherwise. Run n - 1 relaxation passes as usual — that's always enough for every real shortest path to settle. Then run one more pass : if any edge can still be relaxed, some path kept getting cheaper past the point where it should have stopped, which only happens if a negative cycle feeds into it.

Constraints

1 ≤ n ≤ 100
0 ≤ edges.length ≤ 500
edges_i.length == 3
0 ≤ u, v ≤ n - 1
-1000 ≤ w ≤ 1000
0 ≤ src ≤ n - 1

Example

Inputn = 3, edges = [[0, 1, 1], [1, 2, -1], [2, 0, -1]], src = 0

Outputtrue

Explanation The cycle 0 → 1 → 2 → 0 costs 1 + (-1) + (-1) = -1, and it is reachable from src, so it can lower the distance forever.

2. Know the words first

In plain terms

Negative-weight cycle: A loop of edges whose costs add up to less than zero, so looping it again and again keeps lowering the total cost with no floor.

3. Visualize the solution

One pass past the limit still finds an improvement

1∞

2∞

Statusinit

dist[0] = 0; dist[1] and dist[2] start at infinity. n - 1 = 2 regular passes will run.

What happens in this step

pass 1 of 2 begins (n - 1 = 2 regular passes, then 1 extra check)

dist[0] = 0 (source)
dist[1] = dist[2] = ∞

The regular n - 1 passes are enough for every real shortest path to settle. One extra pass afterward checks whether anything is still improving, which would be impossible unless a negative cycle is feeding it.

Step 1 of 4

Steps to visualize

Set dist_src = 0 and every other dist_i = infinity.
Relax every edge, n - 1 times total, the normal Bellman-Ford routine.
Run one extra pass over every edge.
If that extra pass still finds an edge to relax, a negative cycle reachable from src exists.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One pass past the limit still finds an improvement

1∞

2∞

Statusinit

dist[0] = 0; dist[1] and dist[2] start at infinity. n - 1 = 2 regular passes will run.

What happens in this step

pass 1 of 2 begins (n - 1 = 2 regular passes, then 1 extra check)

dist[0] = 0 (source)
dist[1] = dist[2] = ∞

The regular n - 1 passes are enough for every real shortest path to settle. One extra pass afterward checks whether anything is still improving, which would be impossible unless a negative cycle is feeding it.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function hasNegativeCycle(n, edges, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return true;
    }
  }

  return false;
}

Time: O(n * e)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`n = 3, edges = [[0, 1, 1], [1, 2, -1], [2, 0, -1]], src = 0`	`true`	example from the docstring, a reachable negative cycle
`n = 3, edges = [[0, 1, 1], [1, 2, -1]], src = 0`	`false`	negative edges but no cycle at all
`n = 4, edges = [[0, 1, 5], [2, 3, -1], [3, 2, -1]], src = 0`	`false`	a negative cycle exists but src can never reach it
`n = 2, edges = [[0, 1, -100]], src = 0`	`false`	a large negative edge is not a cycle by itself
`n = 2, edges = [[0, 0, -1]], src = 0`	`true`	the smallest possible negative cycle, a self-loop
`n = 3, edges = [[0, 1, 1], [1, 2, 1], [2, 0, 1]], src = 0`	`false`	a cycle exists but its total weight is positive
`n = 3, edges = [[0, 1, 1], [1, 2, -1], [2, 0, 0]], src = 0`	`false`	a cycle summing to exactly zero does not count as negative
`n = 2, edges = [], src = 0`	`false`	a graph with no edges at all

Detect a Negative Cycle