TheAlgorithms/Python · critical · Exception

Negative cycle found

Error message

Negative cycle found

What it means

Raised by bellman_ford (graphs/bellman_ford.py:48) after the relaxation rounds when check_negative_cycle still finds an improvable edge — proof that the graph contains a cycle whose total weight is negative. With a negative cycle, shortest distances are not well-defined (they can be decreased forever), so the function refuses to return misleading values. Note it raises a bare Exception, not ValueError.

Source

Thrown at graphs/bellman_ford.py:48

    >>> g = [{"src": s, "dst": d, "weight": w} for s, d, w in edges + [(1, 3, 5)]]
    >>> bellman_ford(g, 4, 5, 0)
    Traceback (most recent call last):
     ...
    Exception: Negative cycle found
    """
    distance = [float("inf")] * vertex_count
    distance[src] = 0.0

    for _ in range(vertex_count - 1):
        for j in range(edge_count):
            u, v, w = (graph[j][k] for k in ["src", "dst", "weight"])

            if distance[u] != float("inf") and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w

    negative_cycle_exists = check_negative_cycle(graph, distance, edge_count)
    if negative_cycle_exists:
        raise Exception("Negative cycle found")

    return distance


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    V = int(input("Enter number of vertices: ").strip())
    E = int(input("Enter number of edges: ").strip())

    graph: list[dict[str, int]] = [{} for _ in range(E)]

    for i in range(E):
        print("Edge ", i + 1)
        src, dest, weight = (
            int(x)

View on GitHub (pinned to f5988cc097)

Solutions

1. Inspect the graph and fix/remove the negative cycle if it is a data error
2. If negative cycles are expected signal (e.g. arbitrage detection), catch the Exception and report it as a finding
3. For undirected graphs, never use negative weights, or use a shortest-path algorithm that supports them, e.g. Johnson's algorithm after Bellman-Ford detection
4. Wrap the call: bellman_ford distances only when you can guarantee no negative cycle, otherwise use the detection result instead of the distances

Example fix

# before
distances = bellman_ford(graph, vertex_count, edge_count, src)  # crashes on negative cycle

# after
try:
    distances = bellman_ford(graph, vertex_count, edge_count, src)
except Exception as exc:
    if str(exc) == "Negative cycle found":
        distances = None  # handle/report the cycle
    else:
        raise

# Pre-check for negative cycles with the module's own helper if exposed,
# or verify weights: for undirected graphs reject any w < 0 upfront
if any(edge["weight"] < 0 for edge in graph) and is_undirected:
    raise ValueError("negative weights are invalid in undirected graphs")

try:
    dist = bellman_ford(graph, vertex_count, edge_count, src)
except Exception as exc:  # module raises bare Exception
    if "Negative cycle" in str(exc):
        dist = None  # report cycle to user / run arbitrage logic
    else:
        raise

When it happens

Trigger: A directed cycle whose weights sum below zero, e.g. edges 0->1 (w=1), 1->2 (w=1), 2->0 (w=-3). Feeding undirected edges as two directed edges with a negative weight also creates a negative 2-cycle.

Common situations: Currency arbitrage graphs (negative cycles = arbitrage opportunities, often intentional); graphs loaded from files with sign typos; modelling undirected graphs naively with negative weights (each edge becomes a negative cycle with its reverse).

Related errors

• Negative weight cycle detected
• No path from vertex: {self.source_vertex} to vertex: {target
• Algorithm is unable to find solution
• Vertex indexes must be in [0; size).
• You need to set maximum flow algorithm before.

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/ec7bbaac5ba71888. Report an issue: GitHub.