Detecting Negative Cycles, in depth: the Bellman-Ford proof, extracting the cycle, finding every affected vertex, and currency arbitrage

What exactly is broken

A directed graph has vertices, edges u to v, and weights w(u, v). The length of a walk is the sum of its weights. A negative cycle is a closed walk whose length is below zero. If vertex t can be reached from the source s by a walk that passes through a vertex on such a cycle, the infimum of walk lengths from s to t is minus infinity: no finite answer is correct.

Asking for the shortest simple path instead does not help: with negative cycles that problem is NP-hard, since it contains Hamiltonian path. Detection is therefore the gate: either the graph has none and distances are well defined, or it has one and you report it, along with which answers it invalidates.

Negative edges alone are fine. Everything here assumes directed edges; one undirected negative edge is already a negative two-edge cycle.

Why the n-th pass is a proof

Bellman-Ford keeps a distance estimate d(v) for each vertex and repeatedly relaxes every edge: if d(u) + w(u, v) is less than d(v), lower d(v). Two facts make detection work.

First, if there is no negative cycle, every shortest path is simple and has at most n - 1 edges for n vertices. After pass k, every vertex whose shortest path uses at most k edges has its final value. So after n - 1 passes nothing can change, and pass n relaxes nothing.

Second, if there is a negative cycle reachable from the source, some edge on it can always be relaxed. Suppose not: then for every edge (u, v) on the cycle, d(v) is at most d(u) + w(u, v). Add these inequalities around the cycle. Each d appears once on each side and cancels, leaving 0 at most the sum of the cycle's weights, which contradicts the sum being negative. So relaxation never settles, and pass n changes something.

Put together: run n passes. If pass n changes any d, a negative cycle exists. If a pass changes nothing, stop early, because nothing will ever change again. Cost is O(nm) for m edges, which is the price of handling negative weights; when weights are non-negative, Dijkstra's algorithm is much faster and detection is unnecessary.

The virtual source: detect anywhere

Single-source Bellman-Ford only sees cycles it can reach from s. If the question is "does this graph contain a negative cycle anywhere", add a virtual source with a zero-weight edge to every vertex. In code you do not need the extra vertex at all: initialise every d(v) to 0 instead of infinity, which is exactly the state after relaxing those zero edges.

That trick is also the first step of Johnson's all-pairs algorithm, which uses the resulting distances as potentials to re-weight every edge to be non-negative and then runs Dijkstra from each vertex. If the virtual-source run finds a negative cycle, Johnson's algorithm stops there, because no potential function can exist.

Extracting the cycle, not just its existence

Keep a parent array: whenever d(v) is lowered via edge (u, v), set parent(v) = u. Let x be any vertex relaxed in pass n.

x is not necessarily on the cycle. It may sit downstream of it, on a path the cycle keeps making cheaper. But following parent pointers from x backwards must eventually enter a cycle in the parent graph, because a vertex relaxed in pass n has a parent chain that cannot terminate at the source within n steps. After n steps back you are guaranteed to be on the cycle, since a chain of n steps over n vertices must repeat one. From there, follow parents until you return to the start and you have the cycle.

import math
from collections import deque


def find_negative_cycle(n, edges):
    """Bellman-Ford from a virtual source. Returns a list of vertices forming a negative cycle, or None."""
    dist = [0] * n          # virtual source: every vertex starts at distance 0
    parent = [-1] * n
    x = -1
    for _ in range(n):      # n passes: n-1 to converge, the n-th to detect
        x = -1
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                x = v
        if x == -1:
            return None     # a full pass with no change: no negative cycle
    for _ in range(n):      # walk back n steps to be sure we are ON the cycle
        x = parent[x]
    cycle, v = [x], parent[x]
    while v != x:
        cycle.append(v)
        v = parent[v]
    cycle.reverse()
    return cycle


names = ["USD", "EUR", "GBP", "JPY"]
rates = {("USD", "EUR"): 0.92, ("EUR", "GBP"): 0.86, ("GBP", "USD"): 1.28,
         ("USD", "JPY"): 149.0, ("JPY", "EUR"): 0.0061, ("EUR", "USD"): 1.08}
idx = {c: i for i, c in enumerate(names)}
edges = [(idx[a], idx[b], -math.log(r)) for (a, b), r in rates.items()]
cyc = find_negative_cycle(len(names), edges)
print("cycle:", [names[i] for i in cyc])
prod = 1.0
for a, b in zip(cyc, cyc[1:] + cyc[:1]):
    prod *= rates[(names[a], names[b])]
print("product of rates:", round(prod, 6))
print("USD->EUR->GBP product:", round(rates[("USD", "EUR")] * rates[("EUR", "GBP")] * rates[("GBP", "USD")], 6))
print("no-cycle check:", find_negative_cycle(3, [(0, 1, 1), (1, 2, -1), (2, 0, 1)]))

Output when run:

cycle: ['GBP', 'USD', 'JPY', 'EUR']
product of rates: 1.000517
USD->EUR->GBP product: 1.012736
no-cycle check: None

Worked example: currency arbitrage

Trading 1 USD for 0.92 EUR, then EUR for GBP, then back to USD multiplies your money by the product of the three rates. A cycle of trades is profitable when that product exceeds 1. Products become sums under logarithms, so give each edge weight -log(rate): a product above 1 becomes a sum below 0, and arbitrage becomes a negative cycle.

The run found GBP to USD to JPY to EUR and back to GBP, with a product of 1.000517, a 0.05 percent gain. The output also shows a second cycle, USD to EUR to GBP, with a product of 1.012736, which is about 25 times more profitable. Bellman-Ford returned the worse one. That is not a bug. Detection finds a negative cycle, whichever one its parent pointers happen to close first; the edge order decides which.

If you need the best cycle, you are asking a different question. Finding the most negative simple cycle is NP-hard. What is tractable is the minimum mean cycle, the cycle with the most negative average weight per edge, which Karp's algorithm finds in O(nm).

Which vertices are affected

A negative cycle only invalidates answers downstream of it. After n - 1 passes from the real source, any edge that can still be relaxed has its head vertex on, or downstream of, a reachable negative cycle. Every vertex reachable from those heads also has distance minus infinity. A breadth-first search from them marks the full set; all other distances are correct and can be reported.

def minus_infinity_set(n, edges, src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    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
    # anything still relaxable after n-1 passes is on, or downstream of, a negative cycle
    bad = deque(v for u, v, w in edges if dist[u] != INF and dist[u] + w < dist[v])
    neg = set(bad)
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append(v)
    while bad:                      # everything reachable from those vertices is -infinity too
        u = bad.popleft()
        for v in adj[u]:
            if v not in neg:
                neg.add(v)
                bad.append(v)
    return dist, neg

# 0->1 (4), 1->2 (-2), 2->1 (1) is a cycle of weight -1; 3 is reachable from it; 4 is not
g = [(0, 1, 4), (1, 2, -2), (2, 1, 1), (2, 3, 3), (0, 4, 2), (4, 3, 1)]
d, neg = minus_infinity_set(5, g, 0)
print("minus-inf vertices:", sorted(neg))     # prints: minus-inf vertices: [1, 2, 3]

In the test graph, vertices 1 and 2 form a cycle of weight -1, vertex 3 is reachable from the cycle and is marked even though it also has a finite route through vertex 4, and vertices 0 and 4 keep correct finite distances (0 and 2). Vertex 3 is the case people get wrong: one finite path does not make a distance finite when another path can be made arbitrarily short.

To report this set at scale, compress the graph into strongly connected components first (see Tarjan's SCC algorithm). A negative cycle lives inside one component, so you can test components independently and then propagate "minus infinity" through the component DAG in topological order.

SPFA: faster in practice, weaker guarantees

SPFA, the queue-based variant of Bellman-Ford, only re-examines edges out of vertices whose distance just changed. It is often much faster on sparse real graphs, though its worst case is still O(nm) and adversarial inputs reach it. For detection, track how many edges the current best path to each vertex uses. A best path with n or more edges must repeat a vertex, and in a graph without negative cycles best paths are simple, so that count proves a cycle exists.

def spfa_negative_cycle(n, adj):
    dist = [0] * n                  # virtual source again
    cnt = [0] * n                   # edges on the current best path to each vertex
    inq = [True] * n
    q = deque(range(n))
    while q:
        u = q.popleft()
        inq[u] = False
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                cnt[v] = cnt[u] + 1
                if cnt[v] >= n:     # a "shortest" path with n edges repeats a vertex
                    return v        # evidence of a cycle; v itself may be upstream of it
                if not inq[v]:
                    inq[v] = True
                    q.append(v)
    return None

On the currency graph this returns vertex 0. Treat the returned vertex as evidence, not as a cycle member: it may be downstream. To extract the cycle, keep a parent array as before and walk back n steps. Counting enqueues per vertex also works but detects later than the edge-count rule.

Floyd-Warshall and the diagonal

For dense graphs where you want all pairs anyway, Floyd-Warshall detects negative cycles for free. Initialise dist[i][i] = 0 and run the usual triple loop. Afterwards, vertex i lies on a negative cycle if and only if dist[i][i] is below zero. Any pair (i, j) has distance minus infinity if some k with dist[k][k] below zero is reachable from i and reaches j.

With negative cycles present, intermediate values can shrink exponentially with n and overflow fixed-width integers, so stop at the first negative diagonal entry if detection is all you need.

Numerical traps in real data

• Floating point. Log-rates are inexact, and an apparent cycle of weight -1e-15 is rounding noise. Relax only when dist[u] + w < dist[v] - eps with eps chosen from your data's precision, and verify any reported cycle by multiplying the original rates.
• Infinity arithmetic. With a real source, INF + negative is still infinite in floats but wraps or becomes a large finite number with integer sentinels. Always skip edges whose tail is unreached, as the code above does.
• Integer overflow on long chains. Repeated relaxation around a negative cycle drives values down by the cycle weight per pass; with large weights and many passes, 32-bit integers overflow. Use 64-bit values or stop at detection.
• Profitable on paper only. Fold fees and spreads into each edge before detection, not after.

Choosing a method

Unweighted cycle detection, where any cycle counts, is a different and easier problem solved by depth-first search colouring; see cycle detection in directed graphs.

What to do next

1. Run the script above, then reorder the edge list and watch which cycle it reports; that makes the "some cycle, not the best" point concrete.
2. Add the minus-infinity marking to any shortest-path code you own that accepts negative weights, and return those vertices explicitly instead of numbers.
3. If your weights are floats, add an epsilon to the relaxation test and verify every reported cycle against the original data.
4. On large graphs, try SPFA with edge counts and parents, and compare its time with plain Bellman-Ford on your real inputs before switching.
5. If you need the most profitable or best average cycle, implement Karp's minimum mean cycle rather than tweaking detection.