Negative Cycle Detection

Negative Cycle Detection asks a deceptively simple question: in a weighted directed graph, is there a loop whose edge weights add up to a negative number? If so, "shortest path" stops making sense — you could circle that loop forever and your distance would fall to negative infinity. The classic tool is Bellman-Ford, and the trick is one extra pass.

The slow way first

You might try to enumerate every cycle and sum its weights, but a graph can have exponentially many cycles — that blows up fast. Even DFS-based cycle finding gets messy once you have to track running sums along every path.

The question to ask: is there a property that quietly breaks the moment a negative cycle exists? There is. Shortest-path distances stop converging. Bellman-Ford exploits exactly that.

The idea: relax V−1 times, then check once more

Bellman-Ford computes shortest distances by relaxing every edge repeatedly. Relaxing edge (u, v, w) means: if dist[u] + w < dist[v], lower dist[v]. A key theorem says that in a graph with no negative cycle, every shortest path is final after at most V−1 rounds of relaxing all edges.

So run V−1 rounds. Then do one more round. If any edge still relaxes, the distances were not final — which is only possible if a negative cycle keeps dragging them down.

A subtle but important detail: we set every distance to 0 (not just the source). That way the check works even for graphs that are not fully reachable from one source — every vertex gets a fair chance to detect a cycle it sits on.

Walk through it

Step through the animation. The first three passes relax the edges and you can watch the distances around the triangle keep shrinking instead of settling: 4 → 1 → −2 for vertex 1. After V−1 = 3 passes, a clean graph would be frozen. On the V-th pass, edge 3→1 relaxes yet again, which is the smoking gun. We light up the cycle 1→2→3→1 and return True.

Pseudocode

dist = array of size n, all set to 0
repeat n - 1 times:
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
 
# one extra pass
for each edge (u, v, w):
    if dist[u] + w < dist[v]:
        return True          # an edge still relaxed -> negative cycle
return False

The Python solution

def has_negative_cycle(n, edges):
    dist = [0] * n
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # one extra pass: any relaxation => negative cycle
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True
    return False

• dist = [0] * n seeds every vertex at 0 so any cycle anywhere can be caught, not just ones reachable from a single source.
• The outer range(n - 1) runs the V−1 relaxation rounds the theorem guarantees are enough for a cycle-free graph.
• Each inner pass relaxes every edge: dist[u] + w < dist[v] means we found a shorter way into v, so we lower it.
• Lines 8 to 11 are the detector — the one extra pass. If dist[u] + w < dist[v] is still true, distances never converged, so a negative cycle exists and we return True.
• If nothing relaxes on the extra pass, every distance was final after V−1 rounds and there is no negative cycle.

Complexity

The whole algorithm is O(V · E) time and O(V) space for the distance array. Slower than Dijkstra, but Dijkstra cannot handle negative weights at all — Bellman-Ford is the price you pay for that power, plus this free cycle detector.

When this pattern shows up

Practice