What Is a Negative-Weight Cycle? (And Why It Breaks Dijkstra)

You're in an interview. The problem is shortest path. You reach for Dijkstra. It's muscle memory at this point.

Then the interviewer says, "some edge weights might be negative."

Your brain plays a little loading spinner. Your solution just broke. A negative-weight cycle might be the reason, and the painful part is it fails silently. Wrong answers, not exceptions. You might not know anything went wrong until you're halfway through explaining your code.

A Negative-Weight Cycle Is a Loop That Makes You Infinitely Cheap to Reach

A negative-weight cycle is a cycle in a weighted directed graph where the sum of the edge weights along the cycle is negative.

Take this graph:

A --(-5)--> B
B --(3)--> C
C --(1)--> A

Cycle weight: -5 + 3 + 1 = -1

That's a negative-weight cycle. Every time you traverse A → B → C → A, the total cost of your path drops by 1. Do it twice: drops by 2. Ten times: drops by 10. There is no floor. The concept of a "shortest path" stops meaning anything.

If a negative-weight cycle exists on any path from source to destination, the shortest path to that destination is negative infinity. You can always find a cheaper route by looping one more time.

Shortest-path algorithms either break, loop forever, or need a special detection step. Which one depends on the algorithm.

Dijkstra Just Left the Chat

Dijkstra's algorithm is built on one greedy assumption: once you finalize a vertex's distance, no shorter path to it can exist. Pull the smallest-distance vertex from the priority queue, mark it settled, never revisit.

That only works when edge weights are non-negative.

A negative edge means a later path could undercut a distance you already committed to. Dijkstra does not go back and fix it. Wrong answer, not an infinite loop. With a negative cycle it's worse: if the cycle is reachable from the source, the algorithm keeps finding shorter and shorter paths and never terminates. It just spins.

The rule is simple: if your graph has any negative edge weights, Dijkstra is off the table. Not just negative cycles. Any negative edge.

See Dijkstra vs Bellman-Ford for the full comparison of when each algorithm applies.

Surprised Pikachu face staring in shock Every Dijkstra fan when the interviewer casually mentions negative edge weights.

Bellman-Ford Detects Negative Cycles in O(VE)

Bellman-Ford is the right tool when negative edges enter the picture. It relaxes every edge V-1 times, which is enough iterations to find the shortest path in any graph with V vertices (since a simple path visits at most V-1 edges).

def bellman_ford(graph, num_vertices, source):
    dist = [float('inf')] * num_vertices
    dist[source] = 0

    for _ in range(num_vertices - 1):
        for u, v, weight in graph:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight

    # One more pass: if anything still relaxes, a negative cycle exists
    for u, v, weight in graph:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None  # Negative cycle detected

    return dist

The detection logic is on the last loop. If a path of length V or more could still lower a distance, it must contain a cycle. If that cycle improves the cost, it must be negative.

Note the dist[u] != float('inf') guard. Bellman-Ford only detects negative cycles that are reachable from the source vertex. Vertices isolated from the source won't expose their cycles through this method.

Time complexity: O(VE). Space: O(V) for the distance array.

For a deeper walk through the algorithm itself, see Bellman-Ford Algorithm.

Floyd-Warshall Catches What Bellman-Ford Misses

Floyd-Warshall computes shortest paths between all pairs of vertices. When it finishes, check the main diagonal of the distance matrix.

def floyd_warshall(graph, num_vertices):
    dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]

    for i in range(num_vertices):
        dist[i][i] = 0

    for u, v, weight in graph:
        dist[u][v] = weight

    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # Check diagonal for negative cycles
    for i in range(num_vertices):
        if dist[i][i] < 0:
            return None  # Negative cycle detected

    return dist

dist[i][i] starts at 0, representing the trivial path from i back to itself with no edges. After Floyd-Warshall runs, if it's negative, the algorithm found a path from i to i with negative total cost. That path is a negative cycle.

Floyd-Warshall catches negative cycles anywhere in the graph, regardless of which vertex you started from. Bellman-Ford only catches cycles reachable from a specific source. If you need global coverage, this is how.

Time: O(V³). Space: O(V²) for the distance matrix.

See Floyd-Warshall Algorithm for the full derivation and implementation.

Free Money (If the Graph Will Allow It)

This is the negative-weight cycle problem in disguise, and interviewers love it because it looks like finance until you squint.

You're given exchange rates between currencies. Design an algorithm to detect whether a profitable arbitrage sequence exists.

Example rates:

From	To	Rate
USD	EUR	0.85
EUR	GBP	0.88
GBP	USD	1.40

Multiply the rates: 0.85 × 0.88 × 1.40 = 1.0472. Starting with $100, you end with $104.72. Congratulations on your new hobby.

To find this with a shortest-path algorithm, convert multiplication to addition using logarithms:

log(a × b) = log(a) + log(b)

Then negate each weight so that a profitable cycle (product > 1) becomes a negative-weight cycle (sum of negated logs < 0):

import math

def build_arbitrage_graph(rates):
    edges = []
    for (u, v), rate in rates.items():
        edges.append((u, v, -math.log(rate)))
    return edges

Now run Bellman-Ford. If it detects a negative cycle, profitable arbitrage exists.

The key insight is that any problem involving a multiplicative cycle that exceeds 1 can be converted into a negative-weight cycle detection problem through the log transformation.

This shows up in finance, routing optimization, and competitive programming. In an interview, if you see exchange rates and the question asks about cycles, this transformation is the move.

Stonks meme: suited man with arms crossed in front of rising stock chart Running Bellman-Ford on currency exchange rates and finding the negative cycle.

Bellman-Ford or Floyd-Warshall: Which One Do You Actually Need?

Both algorithms detect negative cycles, but they answer slightly different questions.

	Bellman-Ford	Floyd-Warshall
Scope	Cycles reachable from one source	All cycles in the graph
Time	O(VE)	O(V³)
Space	O(V)	O(V²)
Use when	Single source, sparse graph	All-pairs, or need global detection

If the problem asks "can I reach Y from X without hitting a negative cycle," use Bellman-Ford. It starts from a specific source and only explores what's reachable.

If the problem asks "does this graph contain any negative cycle at all" (currency arbitrage is one example where you want to scan the whole graph), Floyd-Warshall's diagonal check is more direct.

In practice, interview questions about negative cycles almost always use Bellman-Ford. Floyd-Warshall tends to appear when you need all-pairs shortest paths anyway and the negative cycle check is an afterthought. See Bellman-Ford vs Floyd-Warshall for the detailed comparison.

What Interviewers Are Actually Testing

When a negative-weight cycle comes up in an interview, the examiner is checking three things.

Whether you know Dijkstra is disqualified the moment negative edge weights appear. Saying "I'll use Dijkstra" after the interviewer mentions negative weights is a signal you're pattern-matching, not reasoning.

Whether you can explain why. Knowing the rule is not enough. You should be able to say that Dijkstra's greedy invariant breaks: once a node is settled, it never gets reconsidered, so a negative edge discovered later can't update it.

Whether you know the Bellman-Ford detection mechanism. The V-1 iterations are for correctness on normal graphs. The V-th pass is the lie-detector test for negative cycles.

"Does your algorithm handle negative cycles" is really asking whether you understand the assumptions baked into shortest-path algorithms and when those assumptions fail.

A strong answer covers: what a negative cycle is and why shortest path becomes undefined, why Dijkstra is wrong here (not just slow), how Bellman-Ford or Floyd-Warshall detects the cycle, and what to return when one is found (null, -infinity, or an explicit error).

The concept is approachable. The gap between knowing it and explaining it clearly under pressure is wider than most candidates expect. SpaceComplexity runs voice-based mock interviews that put exactly these follow-up questions on graph algorithms, with rubric-based feedback on how clearly you communicated the reasoning.

The Short Version

A negative-weight cycle is a cycle where the edge weights sum to a negative number. Any path through it has no well-defined shortest distance. It's negative infinity.
Dijkstra fails with any negative edge weights, not just cycles. Its greedy invariant requires non-negative weights or the settled distances are wrong.
Bellman-Ford detects negative cycles with a V-th relaxation pass. It only catches cycles reachable from the source.
Floyd-Warshall detects negative cycles by checking dist[i][i] < 0 after completion. It catches cycles anywhere in the graph.
Currency arbitrage is this problem in disguise. Convert exchange rates to edge weights with -log(rate) and run Bellman-Ford.