{"record":{"id":"ec7bbaac5ba71888","repo":"TheAlgorithms/Python","slug":"negative-cycle-found","errorCode":null,"errorMessage":"Negative cycle found","messagePattern":"Negative cycle found","errorType":"exception","errorClass":"Exception","httpStatus":null,"severity":"critical","filePath":"graphs/bellman_ford.py","lineNumber":48,"sourceCode":"    >>> g = [{\"src\": s, \"dst\": d, \"weight\": w} for s, d, w in edges + [(1, 3, 5)]]\n    >>> bellman_ford(g, 4, 5, 0)\n    Traceback (most recent call last):\n     ...\n    Exception: Negative cycle found\n    \"\"\"\n    distance = [float(\"inf\")] * vertex_count\n    distance[src] = 0.0\n\n    for _ in range(vertex_count - 1):\n        for j in range(edge_count):\n            u, v, w = (graph[j][k] for k in [\"src\", \"dst\", \"weight\"])\n\n            if distance[u] != float(\"inf\") and distance[u] + w < distance[v]:\n                distance[v] = distance[u] + w\n\n    negative_cycle_exists = check_negative_cycle(graph, distance, edge_count)\n    if negative_cycle_exists:\n        raise Exception(\"Negative cycle found\")\n\n    return distance\n\n\nif __name__ == \"__main__\":\n    import doctest\n\n    doctest.testmod()\n\n    V = int(input(\"Enter number of vertices: \").strip())\n    E = int(input(\"Enter number of edges: \").strip())\n\n    graph: list[dict[str, int]] = [{} for _ in range(E)]\n\n    for i in range(E):\n        print(\"Edge \", i + 1)\n        src, dest, weight = (\n            int(x)","sourceCodeStart":30,"sourceCodeEnd":66,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/graphs/bellman_ford.py#L30-L66","documentation":"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.","triggerScenarios":"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.","commonSituations":"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).","solutions":["Inspect the graph and fix/remove the negative cycle if it is a data error","If negative cycles are expected signal (e.g. arbitrage detection), catch the Exception and report it as a finding","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","Wrap the call: bellman_ford distances only when you can guarantee no negative cycle, otherwise use the detection result instead of the distances"],"exampleFix":"# before\ndistances = bellman_ford(graph, vertex_count, edge_count, src)  # crashes on negative cycle\n\n# after\ntry:\n    distances = bellman_ford(graph, vertex_count, edge_count, src)\nexcept Exception as exc:\n    if str(exc) == \"Negative cycle found\":\n        distances = None  # handle/report the cycle\n    else:\n        raise","handlingStrategy":"try-catch","validationCode":"# Pre-check for negative cycles with the module's own helper if exposed,\n# or verify weights: for undirected graphs reject any w < 0 upfront\nif any(edge[\"weight\"] < 0 for edge in graph) and is_undirected:\n    raise ValueError(\"negative weights are invalid in undirected graphs\")","typeGuard":null,"tryCatchPattern":"try:\n    dist = bellman_ford(graph, vertex_count, edge_count, src)\nexcept Exception as exc:  # module raises bare Exception\n    if \"Negative cycle\" in str(exc):\n        dist = None  # report cycle to user / run arbitrage logic\n    else:\n        raise","preventionTips":["Never use negative weights in undirected graphs (each edge forms a negative cycle with its reverse)","Treat a negative-cycle exception as data, not just an error, in arbitrage-style applications","Validate edge weight signs at load time"],"tags":["graphs","shortest-path","negative-cycle","bellman-ford"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}