{"record":{"id":"539e5ac19c95510e","repo":"TheAlgorithms/Python","slug":"negative-weight-cycle-detected","errorCode":null,"errorMessage":"Negative weight cycle detected","messagePattern":"Negative weight cycle detected","errorType":"exception","errorClass":"ValueError","httpStatus":null,"severity":"critical","filePath":"graphs/johnson.py","lineNumber":39,"sourceCode":"    \"\"\"\n    Bellman-Ford relaxation to compute potentials h[v] for all vertices.\n    Raises ValueError if a negative weight cycle exists.\n    \"\"\"\n    dist: dict[Node, float] = dict.fromkeys(nodes, 0.0)\n    n = len(nodes)\n\n    for _ in range(n - 1):\n        updated = False\n        for u, v, w in edges:\n            if dist[u] + w < dist[v]:\n                dist[v] = dist[u] + w\n                updated = True\n        if not updated:\n            break\n    else:\n        for u, v, w in edges:\n            if dist[u] + w < dist[v]:\n                raise ValueError(\"Negative weight cycle detected\")\n    return dist\n\n\ndef _dijkstra(\n    start: Node,\n    nodes: list[Node],\n    graph: adjacency,\n    potentials: dict[Node, float],\n) -> dict[Node, float]:\n    \"\"\"\n    Dijkstra over reweighted graph, using potentials h to make weights non-negative.\n    Returns distances from start in the reweighted space.\n    \"\"\"\n    inf = float(\"inf\")\n    dist: dict[Node, float] = dict.fromkeys(nodes, inf)\n    dist[start] = 0.0\n    heap: list[tuple[float, Node]] = [(0.0, start)]\n","sourceCodeStart":21,"sourceCodeEnd":57,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/graphs/johnson.py#L21-L57","documentation":"Raised by the Bellman-Ford relaxation step inside Johnson's algorithm (graphs/johnson.py). After n-1 full relaxation passes (with an early-exit when a pass changes nothing), one extra pass still finds an improvable distance — mathematically only possible if a cycle with negative total weight is reachable from the super-source. Shortest distances are undefined on such graphs, so the algorithm aborts.","triggerScenarios":"Calling johnson(graph) where the edge list contains a reachable negative-weight cycle, e.g. edges a->b (-1), b->c (-1), c->a (-1). Even if the cycle sits in one component, the super-source connects to every node, so any negative cycle anywhere triggers it.","commonSituations":"Feeding distance/cost matrices where 'discount' edges sum negatively around a loop; data-entry bugs flipping weight signs; financial arbitrage-style graphs where negative cycles are semantically meaningful but unsupported by this implementation.","solutions":["Detect and report the cycle: run Bellman-Ford separately and trace vertices still relaxing to identify the offending edges.","Fix the data if the negative cycle is a bug (check sign conventions on weights).","If negative cycles are expected input, use an algorithm that supports them (e.g. Floyd-Warshall with cycle detection) or remove/penalize cycle edges before calling johnson.","Wrap the call in try/except ValueError and degrade gracefully (skip component or raise a domain-specific error)."],"exampleFix":"# before\nresult = johnson(graph)  # ValueError: Negative weight cycle detected\n\n# after\nfrom graphs.johnson import johnson\ntry:\n    result = johnson(graph)\nexcept ValueError as exc:\n    if \"Negative weight cycle\" in str(exc):\n        raise GraphHasNegativeCycleError(graph) from exc\n    raise","handlingStrategy":"try-catch","validationCode":"def find_negative_cycle(nodes, edges) -> list | None:\n    dist = {v: 0.0 for v in nodes}\n    for _ in range(len(nodes)):\n        updated = False\n        for u, v, w in edges:\n            if dist[u] + w < dist[v]:\n                dist[v] = dist[u] + w\n                updated = True\n        if not updated:\n            return None\n    return [e for e in edges if dist[e[0]] + e[2] < dist[e[1]]]","typeGuard":null,"tryCatchPattern":"try:\n    result = johnson(graph)\nexcept ValueError as exc:\n    if \"Negative weight cycle\" in str(exc):\n        raise DomainError(\"graph contains a negative-weight cycle\") from exc\n    raise","preventionTips":["Run a Bellman-Ford cycle check before calling johnson on untrusted weights.","Audit weight signs at ingestion; negative cycles are usually data bugs.","Remember the super-source reaches every node, so no component is exempt."],"tags":["graph","shortest-path","johnson","bellman-ford","negative-cycle"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}