{"record":{"id":"f104eeddb8479405","repo":"TheAlgorithms/Python","slug":"negative-edge-weight-after-reweighting-numeric-er","errorCode":null,"errorMessage":"Negative edge weight after reweighting: numeric error","messagePattern":"Negative edge weight after reweighting: numeric error","errorType":"exception","errorClass":"ValueError","httpStatus":null,"severity":"error","filePath":"graphs/johnson.py","lineNumber":65,"sourceCode":"    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\n    while heap:\n        d_u, u = heapq.heappop(heap)\n        if d_u > dist[u]:\n            continue\n        for v, w in graph.get(u, []):\n            w_prime = w + potentials[u] - potentials[v]\n            if w_prime < 0:\n                raise ValueError(\n                    \"Negative edge weight after reweighting: numeric error\"\n                )\n            new_dist = d_u + w_prime\n            if new_dist < dist[v]:\n                dist[v] = new_dist\n                heapq.heappush(heap, (new_dist, v))\n    return dist\n\n\ndef johnson(graph: adjacency) -> dict[Node, dict[Node, float]]:\n    \"\"\"\n    Compute all-pairs shortest paths using Johnson's algorithm.\n\n    Reference:\n        https://en.wikipedia.org/wiki/Johnson%27s_algorithm\n\n    Args:\n        graph: adjacency list {u: [(v, weight), ...], ...}","sourceCodeStart":47,"sourceCodeEnd":83,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/graphs/johnson.py#L47-L83","documentation":"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.","triggerScenarios":"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.","commonSituations":"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.","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."],"exampleFix":"# before\ndist = johnson(graph)  # float weights -> numeric error\n\n# after\n# scale float weights to exact ints before building the graph\nscaled = {\n    u: [(v, round(w * 1000)) for v, w in nbrs] for u, nbrs in graph.items()\n}\ndist = johnson(scaled)  # integer reweighting is exact","handlingStrategy":"validation","validationCode":"def weights_safe_for_johnson(graph) -> bool:\n    # reject non-numeric / inconsistent weights that stress reweighting\n    return all(\n        isinstance(w, (int, float)) and w > -float(\"inf\")\n        for nbrs in graph.values()\n        for _, w in nbrs\n    )","typeGuard":null,"tryCatchPattern":"try:\n    dist = johnson(graph)\nexcept ValueError as exc:\n    if \"numeric error\" in str(exc):\n        dist = johnson(_scale_to_int(graph))  # exact integer reweighting\n    else:\n        raise","preventionTips":["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."],"tags":["graph","shortest-path","johnson","floating-point","dijkstra"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}