What causes "Negative edge weight after reweighting: numeric error" in TheAlgorithms/Python?

Snap near-zero negatives to zero instead of relying on exact arithmetic: check `w_prime < -1e-9` (epsilon tolerance) in a local copy if the invariant violation is purely numeric.

TheAlgorithms/Python · error · ValueError

Negative edge weight after reweighting: numeric error

Error message

Negative edge weight after reweighting: numeric error

What it means

Raised inside the Dijkstra phase of Johnson's algorithm (graphs/johnson.py). After Bellman-Ford computes potentials h, every edge is reweighted to w' = w + h[u] - h[v], which theory guarantees is >= 0 when no negative cycle exists. If w' comes out negative here, floating-point rounding (or inconsistent weights that make Bellman-Ford's guarantee marginal) broke the invariant, and Dijkstra cannot proceed safely.

Source

Thrown at graphs/johnson.py:65

    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)]

    while heap:
        d_u, u = heapq.heappop(heap)
        if d_u > dist[u]:
            continue
        for v, w in graph.get(u, []):
            w_prime = w + potentials[u] - potentials[v]
            if w_prime < 0:
                raise ValueError(
                    "Negative edge weight after reweighting: numeric error"
                )
            new_dist = d_u + w_prime
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    return dist


def johnson(graph: adjacency) -> dict[Node, dict[Node, float]]:
    """
    Compute all-pairs shortest paths using Johnson's algorithm.

    Reference:
        https://en.wikipedia.org/wiki/Johnson%27s_algorithm

    Args:
        graph: adjacency list {u: [(v, weight), ...], ...}

View on GitHub (pinned to f5988cc097)

Solutions

Snap near-zero negatives to zero instead of relying on exact arithmetic: check `w_prime < -1e-9` (epsilon tolerance) in a local copy if the invariant violation is purely numeric.
Scale weights to integers (e.g. cents instead of dollars) so all arithmetic is exact.
Validate up front that no negative cycle exists and weights are consistent before calling johnson.
If floats are essential, consider a Johnson variant with an epsilon clamp or use Floyd-Warshall.

Example fix

# before
dist = johnson(graph)  # float weights -> numeric error

# after
# scale float weights to exact ints before building the graph
scaled = {
    u: [(v, round(w * 1000)) for v, w in nbrs] for u, nbrs in graph.items()
}
dist = johnson(scaled)  # integer reweighting is exact

Defensive patterns

Strategy: validation

Validate before calling

def weights_safe_for_johnson(graph) -> bool:
    # reject non-numeric / inconsistent weights that stress reweighting
    return all(
        isinstance(w, (int, float)) and w > -float("inf")
        for nbrs in graph.values()
        for _, w in nbrs
    )

Try / catch

try:
    dist = johnson(graph)
except ValueError as exc:
    if "numeric error" in str(exc):
        dist = johnson(_scale_to_int(graph))  # exact integer reweighting
    else:
        raise

Prevention

Prefer integer weights (scale floats by a fixed factor) for exact reweighting arithmetic.
Validate that no negative cycles exist first — the invariant assumes valid potentials.
Avoid mixed int/float weights in one graph.

When it happens

Trigger: Using float weights where tiny rounding errors make a reweighted edge dip just below zero (e.g. w' == -1e-16); weights that mix ints and floats inconsistently; graphs where some shortest-path distances are -inf-adjacent due to borderline cycles.

Common situations: Real-valued weights from measurements or monetary computations accumulated over many edges; porting from int to float weights; very long paths where floating-point error accumulates in the potentials.

Related errors

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