TheAlgorithms/Python · critical · ValueError

Negative weight cycle detected

Error message

Negative weight cycle detected

What it means

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.

Source

Thrown at graphs/johnson.py:39

    """
    Bellman-Ford relaxation to compute potentials h[v] for all vertices.
    Raises ValueError if a negative weight cycle exists.
    """
    dist: dict[Node, float] = dict.fromkeys(nodes, 0.0)
    n = len(nodes)

    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break
    else:
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                raise ValueError("Negative weight cycle detected")
    return dist


def _dijkstra(
    start: Node,
    nodes: list[Node],
    graph: adjacency,
    potentials: dict[Node, float],
) -> dict[Node, float]:
    """
    Dijkstra over reweighted graph, using potentials h to make weights non-negative.
    Returns distances from start in the reweighted space.
    """
    inf = float("inf")
    dist: dict[Node, float] = dict.fromkeys(nodes, inf)
    dist[start] = 0.0
    heap: list[tuple[float, Node]] = [(0.0, start)]

View on GitHub (pinned to f5988cc097)

Solutions

1. Detect and report the cycle: run Bellman-Ford separately and trace vertices still relaxing to identify the offending edges.
2. Fix the data if the negative cycle is a bug (check sign conventions on weights).
3. 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.
4. Wrap the call in try/except ValueError and degrade gracefully (skip component or raise a domain-specific error).

Example fix

# before
result = johnson(graph)  # ValueError: Negative weight cycle detected

# after
from graphs.johnson import johnson
try:
    result = johnson(graph)
except ValueError as exc:
    if "Negative weight cycle" in str(exc):
        raise GraphHasNegativeCycleError(graph) from exc
    raise

def find_negative_cycle(nodes, edges) -> list | None:
    dist = {v: 0.0 for v in nodes}
    for _ in range(len(nodes)):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            return None
    return [e for e in edges if dist[e[0]] + e[2] < dist[e[1]]]

try:
    result = johnson(graph)
except ValueError as exc:
    if "Negative weight cycle" in str(exc):
        raise DomainError("graph contains a negative-weight cycle") from exc
    raise

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Negative cycle found
• Negative edge weight after reweighting: numeric error
• No path from vertex: {self.source_vertex} to vertex: {target
• Incorrect input: {vertex} does not exist in this graph.
• Incorrect input: The edge does NOT exist between {source_ver

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