Detecting Negative Cycles in Graphs

A negative cycle is a cycle in a weighted directed graph whose edge weights sum to a negative value. When such a cycle is reachable from a source vertex, the concept of a “shortest path” breaks down because you can keep traversing the cycle to reduce the total cost indefinitely.

Detecting negative cycles is critical in several domains:

• Currency arbitrage: a sequence of exchanges that yields more money than you started with.
• Game AI: finding infinite resource loops.
• Network routing: identifying unstable routing configurations.

Why shortest-path algorithms fail

Dijkstra’s algorithm assumes all edge weights are non-negative. When a negative cycle exists, Dijkstra may loop forever or return incorrect results. Bellman-Ford handles negative edges gracefully and, with one extra pass, can detect whether a negative cycle exists.

Bellman-Ford refresher

Bellman-Ford relaxes every edge |V| - 1 times. After |V| - 1 iterations the shortest-path estimates are final unless a negative cycle is reachable.

def bellman_ford(n: int, edges: list[tuple[int, int, float]], src: int):
    """
    Returns (dist, predecessor) arrays.
    dist[v] = shortest distance from src to v.
    If no negative cycle, all values are optimal after n-1 passes.
    """
    INF = float('inf')
    dist = [INF] * n
    pred = [-1] * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u

    return dist, pred

Time complexity: O(V * E)

Space complexity: O(V)

Detecting a negative cycle: the nth relaxation

The key insight is straightforward: after |V| - 1 relaxation passes, all shortest distances are finalized if no negative cycle exists. If we run one more pass and any distance can still be reduced, a negative cycle is reachable.

def has_negative_cycle(n: int, edges: list[tuple[int, int, float]], src: int) -> bool:
    """
    Returns True if a negative cycle is reachable from src.
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    # Standard n-1 relaxation passes
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # nth pass: if any edge can still be relaxed, negative cycle exists
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return True

    return False

Why does this work?

In a graph without negative cycles, the shortest path between any two vertices uses at most |V| - 1 edges (a simple path). After |V| - 1 relaxation rounds, every shortest path has been discovered. If the nth round still finds a shorter path, that path must use |V| or more edges, which means it revisits a vertex, forming a cycle that reduces cost — a negative cycle.

Tracing the actual negative cycle

Knowing a negative cycle exists is often not enough. We need to find the cycle itself. The approach:

1. Run the nth relaxation pass and record any vertex v that gets relaxed.
2. Follow predecessors from v for |V| steps to ensure you land on a vertex that is definitely on the cycle.
3. Trace back from that vertex until you revisit it.

def find_negative_cycle(n: int, edges: list[tuple[int, int, float]]):
    """
    Returns a list of vertices forming a negative cycle, or empty list
    if none exists.
    """
    INF = float('inf')
    dist = [0] * n          # start all at 0 to detect any reachable cycle
    pred = [-1] * n

    changed = -1
    for i in range(n):
        changed = -1
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u
                changed = v

    if changed == -1:
        return []            # no negative cycle

    # Walk back n steps to land inside the cycle
    v = changed
    for _ in range(n):
        v = pred[v]

    # Trace the cycle
    cycle = []
    cur = v
    while True:
        cycle.append(cur)
        cur = pred[cur]
        if cur == v:
            cycle.append(v)
            break

    cycle.reverse()
    return cycle

Key detail: We initialize all distances to 0 instead of infinity. This lets us detect negative cycles anywhere in the graph, not just those reachable from a single source.

Finding nodes affected by negative cycles

Sometimes you need to know which specific nodes have their shortest path affected (i.e., can reach negative infinity). Run V additional passes after the standard V-1 passes, propagating negative infinity to all reachable nodes:

def bellman_ford_affected_nodes(
    n: int, edges: list[tuple[int, int, float]], source: int
) -> list[float]:
    """
    Returns distances, with -inf for nodes affected by negative cycles.
    """
    dist = [float('inf')] * n
    dist[source] = 0

    # V-1 passes
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # V more passes to propagate negative cycle effects
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = float('-inf')
            if dist[u] == float('-inf'):
                dist[v] = float('-inf')

    return dist

Currency arbitrage detection

One of the most famous applications of negative cycle detection is currency arbitrage. Given exchange rates between currencies, can you start with one unit of a currency, perform a series of exchanges, and end up with more than one unit of the same currency?

Modelling the problem

Given exchange rates rate[i][j] (1 unit of currency i buys rate[i][j] units of currency j):

• We want to find if a cycle c1 -> c2 -> ... -> c1 exists where rate[c1][c2] * rate[c2][c3] * ... * rate[ck][c1] {'>'} 1.
• Taking the negative logarithm of each rate transforms the multiplicative problem into an additive one: we need a cycle where the sum of -log(rate) values is negative.

Why logarithms?

Exchange rates are multiplicative: starting with $1, exchanging USD->EUR->GBP->USD gives you rate1 * rate2 * rate3 dollars. Arbitrage exists when the product exceeds 1. Taking -log of each rate converts multiplication to addition: -log(rate1) + (-log(rate2)) + (-log(rate3)). If this sum is negative, the product of rates exceeds 1, meaning arbitrage exists.

import math

def detect_arbitrage(rates: list[list[float]]) -> bool:
    """
    rates[i][j] = exchange rate from currency i to currency j.
    Returns True if an arbitrage opportunity exists.
    """
    n = len(rates)
    edges = []

    for i in range(n):
        for j in range(n):
            if i != j and rates[i][j] > 0:
                # Transform: weight = -log(rate)
                weight = -math.log(rates[i][j])
                edges.append((i, j, weight))

    # Use Bellman-Ford with all distances starting at 0
    dist = [0.0] * n

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True

    return False

Finding the arbitrage cycle

def find_arbitrage_cycle(
    currencies: list[str],
    rates: dict[tuple[str, str], float]
) -> list[str]:
    """Find the actual arbitrage cycle, if it exists."""
    n = len(currencies)
    currency_idx = {c: i for i, c in enumerate(currencies)}

    edges = []
    for (from_c, to_c), rate in rates.items():
        u = currency_idx[from_c]
        v = currency_idx[to_c]
        edges.append((u, v, -math.log(rate)))

    dist = [float('inf')] * n
    parent = [-1] * n
    dist[0] = 0

    last_updated = -1

    for i in range(n):
        last_updated = -1
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                last_updated = v

    if last_updated == -1:
        return []  # no arbitrage

    # Trace back the cycle
    node = last_updated
    for _ in range(n):
        node = parent[node]

    cycle = []
    current = node
    while True:
        cycle.append(currencies[current])
        current = parent[current]
        if current == node:
            cycle.append(currencies[current])
            break

    cycle.reverse()
    return cycle

Example

Rates: USD->EUR: 0.85, EUR->GBP: 0.88, GBP->USD: 1.40

Product: 0.85 * 0.88 * 1.40 = 1.0472 > 1

Edge weights: -log(0.85) = 0.163, -log(0.88) = 0.128, -log(1.40) = -0.336

Cycle weight: 0.163 + 0.128 + (-0.336) = -0.045 < 0

Negative cycle detected. Arbitrage is possible: start with $1000, get $1047.20 after one round.

The SPFA algorithm

Shortest Path Faster Algorithm (SPFA) is a queue-based optimization of Bellman-Ford. It only relaxes edges from vertices whose distances have recently changed, often running much faster in practice.

For negative cycle detection, we track how many times each vertex enters the queue. If any vertex enters more than |V| times, a negative cycle exists.

from collections import deque

def spfa_negative_cycle(n: int, adj: list[list[tuple[int, float]]], src: int) -> bool:
    """
    adj[u] = list of (v, weight) edges from u.
    Returns True if a negative cycle is reachable from src.
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    in_queue = [False] * n
    count = [0] * n          # times each vertex entered the queue

    queue = deque([src])
    in_queue[src] = True
    count[src] = 1

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1

                    if count[v] > n:
                        return True   # negative cycle detected

    return False

SPFA complexity

Case	Time
Best case	O(E)
Average	O(E)
Worst case	O(V * E)
Space	O(V)

SPFA degrades to Bellman-Ford on adversarial inputs, but for random graphs it is significantly faster. Some competitive programmers avoid SPFA because it can be forced into worst-case behavior with crafted inputs.

Cheapest Flights with K Stops (LeetCode 787)

A modified Bellman-Ford where you limit the number of edges (stops):

def find_cheapest_price(
    n: int, flights: list[list[int]], src: int, dst: int, k: int
) -> int:
    """
    LeetCode 787: Find cheapest flight with at most k stops.
    Use Bellman-Ford with exactly k+1 passes.
    """
    dist = [float('inf')] * n
    dist[src] = 0

    # k stops = k+1 edges maximum
    for _ in range(k + 1):
        # Important: use a copy to avoid using updated values
        # from the same pass
        new_dist = dist[:]

        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < new_dist[v]:
                new_dist[v] = dist[u] + w

        dist = new_dist

    return dist[dst] if dist[dst] != float('inf') else -1

Note the critical detail: we use a copy of dist for each pass. Without the copy, we might use a distance updated in the current pass, effectively using more edges than allowed.

Detecting negative cycles in all components

When the graph is disconnected, a single-source Bellman-Ford only checks cycles reachable from the source. Two approaches handle this:

Approach 1: virtual super-source

Add a virtual vertex S with zero-weight edges to every other vertex, then run Bellman-Ford from S.

def negative_cycle_any_component(n: int, edges: list[tuple[int, int, float]]) -> bool:
    """
    Detects negative cycle in any connected component.
    """
    # Add super-source with id = n
    extended_edges = edges[:]
    for v in range(n):
        extended_edges.append((n, v, 0))

    return has_negative_cycle(n + 1, extended_edges, n)

Approach 2: initialize all distances to zero

Set dist[v] = 0 for all v. This simulates having a super-source without actually adding one, as we did in the find_negative_cycle function above.

Shortest path in DAGs with negative weights

A graph can have negative edges without having negative cycles. A DAG (no cycles at all) can have negative edges, and shortest paths are well-defined. Use topological sort + relaxation for O(V + E) performance:

def shortest_path_dag_negative(
    n: int, adj: list[list[tuple[int, int]]], source: int
) -> list[float]:
    """
    Shortest path in a DAG (can have negative edges).
    Topological sort + relaxation. O(V + E).
    """
    from collections import deque

    in_degree = [0] * n
    for u in range(n):
        for v, w in adj[u]:
            in_degree[v] += 1

    # Topological sort
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v, w in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # Relax in topological order
    dist = [float('inf')] * n
    dist[source] = 0

    for u in topo_order:
        if dist[u] == float('inf'):
            continue
        for v, w in adj[u]:
            dist[v] = min(dist[v], dist[u] + w)

    return dist

This is O(V + E), much faster than Bellman-Ford, but only works for DAGs.

Negative cycles in undirected graphs

An undirected graph can have a negative cycle if any edge has a negative weight. Why? Traversing a negative-weight edge back and forth creates a cycle of weight 2w {'<'} 0. So negative cycle detection in undirected graphs is trivially a scan for any negative edge weight.

Common pitfalls

1. Floating-point precision: When using log-transformed weights (as in arbitrage), floating-point errors can cause false positives. Use an epsilon threshold: dist[u] + w {'<'} dist[v] - 1e-9.

2. Unreachable cycles: Standard Bellman-Ford from a single source only detects cycles reachable from that source. Use the super-source technique for global detection.

3. Confusing “has negative edges” with “has negative cycle”: A graph can have negative edges without any negative cycle. Bellman-Ford handles negative edges fine; it is only negative cycles that are problematic.

4. Forgetting the INF check: When relaxing dist[u] + w {'<'} dist[v], ensure dist[u] != INF to avoid arithmetic on infinity.

5. Not copying the distance array in K-stops problems: Without copying, you may use distances updated in the same pass, effectively using more edges than allowed.

Big-O summary

Algorithm	Time	Space	Detects cycle?
Bellman-Ford + nth pass	O(V * E)	O(V)	Yes
SPFA	O(V * E)*	O(V)	Yes
Floyd-Warshall (all-pairs)	O(V^3)	O(V^2)	Yes (diagonal)
Dijkstra	O(E log V)	O(V)	No
DAG topo sort + relax	O(V + E)	O(V)	N/A (no cycles)

*SPFA is O(E) on average but O(V * E) worst case.

Practice problems

Problem	Difficulty	Key Concept
LeetCode 787: Cheapest Flights K Stops	Medium	Limited Bellman-Ford
LeetCode 743: Network Delay Time	Medium	Shortest path (Dijkstra or BF)
LeetCode 1334: Find City with Smallest Neighbors	Medium	All-pairs shortest path
Negative Weight Cycle - GeeksforGeeks	Medium	Standard negative cycle
Shortest Path with Negative Weights - CSES	Hard	Negative cycles + infinite paths

Key takeaways

• Run Bellman-Ford for |V| iterations instead of |V| - 1. If the nth pass still relaxes an edge, a negative cycle exists.
• SPFA provides a practical speedup: track queue-entry counts and flag a cycle when any vertex exceeds |V| entries.
• Currency arbitrage maps directly to negative cycle detection via log-transformation of exchange rates.
• For disconnected graphs, use a virtual super-source or initialize all distances to zero.
• For DAGs with negative weights, use topological sort + relaxation in O(V + E) instead of Bellman-Ford.
• SPFA is faster in practice but has the same worst case. Use it when speed matters, but understand its limitations on adversarial inputs.