A cost function assembled from several terms will eventually produce a negative one, and the effect is a router that returns paths that are quietly not shortest. This page covers where negatives come from and how to prevent them structurally, as part of custom cost functions for routing solvers within Python Routing Engines & Isochrone Mapping.

Two sources account for nearly all of them: a credit term that is allowed to exceed the cost it offsets, and a multiplier applied to an already-negative intermediate. Both are easy to prevent and neither announces itself.

When to use this approach

Apply the guard whenever the cost function contains subtraction or a coefficient that can be configured negative. In practice that is any model with regenerative braking, any model with a preference bonus for a road class, and any model whose coefficients are exposed for tuning — because a coefficient a user can set is a coefficient a user will eventually set negative.

Models built purely from positive multiplicative penalties cannot go negative and need only the zero floor.

Where a credit takes the weight below zero An edge with a base cost of 68 seconds accumulates a surface penalty and a grade penalty, then a regeneration credit of 96 seconds is subtracted. The credit exceeds everything above it and the final weight lands at minus 11 seconds. Cost build-up on one downhill edge, EV profile zero base travel +68 s surface penalty +14 s grade term +3 s regen credit −96 s — uncapped final weight −11 s — Dijkstra now returns wrong answers Nothing raises — some routes are simply not shortest.

Implementation

The structural fix is to cap credits at the cost they offset, before any floor is applied.

# requires: numpy (pip install numpy)
import numpy as np

FLOOR_S = 0.1          # strictly positive, well below any real edge cost


def compose_weight(base_s: np.ndarray, penalties_s: np.ndarray,
                   credits_s: np.ndarray) -> tuple[np.ndarray, dict]:
    """Sum cost terms with credits capped and a positive floor enforced."""
    gross = base_s + penalties_s
    # A credit can offset the cost it applies to; it cannot create free travel
    capped = np.minimum(credits_s, gross * 0.9)
    raw = gross - capped

    floored = np.maximum(raw, FLOOR_S)
    stats = {
        "credit_capped": int((credits_s > gross * 0.9).sum()),
        "floored": int((raw < FLOOR_S).sum()),
        "min_raw": float(raw.min()),
    }
    return floored, stats

Capping at ninety percent of gross rather than at gross itself leaves every edge with a residual cost proportional to its length, which keeps the router’s ordering sensible on long downhill stretches. Capping at exactly gross would make a steep descent free, and a free edge is the zero-weight problem by another route.

Returning statistics rather than clamping silently is the other half. A model that floors ten edges has a rounding artefact; one that floors ten thousand has a sign error somewhere, and the only difference visible from the outside is the count.

# requires: numpy (pip install numpy)
import numpy as np


def assert_positive(weights: np.ndarray, *, name: str = "weight") -> None:
    """Refuse to hand a solver anything it cannot process correctly."""
    if not np.isfinite(weights).all():
        raise ValueError(f"{name} contains NaN or inf")
    bad = weights <= 0
    if bad.any():
        idx = np.flatnonzero(bad)[:5]
        raise ValueError(
            f"{name} has {bad.sum()} non-positive entries; first indices {idx.tolist()}"
        )

Running this immediately before the graph is handed to a solver — rather than inside the cost function — catches weights that were fine when computed and were later modified by a traffic overlay or an incident penalty applied with the wrong sign.

For multiplicative models the equivalent guard is on the multiplier rather than the sum:

# requires: numpy (pip install numpy)
import numpy as np


def safe_multiplier(factor: np.ndarray, *, lo: float = 0.25,
                    hi: float = 8.0) -> np.ndarray:
    """Bound a cost multiplier so it can neither invert nor explode the weight."""
    if (factor < 0).any():
        raise ValueError("negative multiplier — check the sign of the coefficient")
    return np.clip(factor, lo, hi)

Raising on a negative multiplier rather than clipping it is deliberate: a negative multiplier is never a tuning choice, it is always a sign error, and clipping it to lo would produce a plausible-looking weight from a genuinely broken configuration.

There is a second-order effect worth understanding before reaching for the floor. Clamping a negative weight to a small positive value does not merely fix that edge; it makes the edge extremely attractive, because a cost of 0.1 seconds is far cheaper than any genuine alternative. A graph with a few hundred floored edges will route through all of them preferentially, producing a set of implausible detours that share no obvious feature except that they are all cheap. This is why the clamp count belongs in the build report rather than in a debug log — the symptom looks like a routing quality problem long before anyone suspects the cost function.

Key parameters and tuning

Parameter Recommended value Notes
FLOOR_S 0.1 s Strictly positive, far below any real edge cost
Credit cap 90 % of gross Leaves a length-proportional residual so ordering stays sensible
Multiplier bounds 0.25 to 8.0 Wide enough for real penalties, narrow enough to catch errors
Negative multiplier raise Never a tuning choice; always a sign error
Clamp reporting count per build Ten is an artefact, ten thousand is a bug
Assertion point immediately before the solver Catches overlays applied after composition
Dtype float64 during composition float32 rounding can turn a small positive into zero

Integration points

With EV energy models. Regeneration is the most common source of legitimate credits, and it is exactly where the cap matters. The physical cap — recovery limited by motor and pack acceptance — is described in modeling battery-range constraints for EV fleets, and modelling it properly usually removes the negative weights without needing the floor at all.

With incident overlays. A live traffic layer that applies a speed increase on a cleared incident can subtract from an already-low weight. Because overlays are applied after composition, the assertion has to run after them too — see traffic-incident-triggered re-routing.

With engine profiles. OSRM and Valhalla both reject non-positive weights at build time, so a negative weight surfaces there as a preprocessing failure rather than a wrong route. That is a better outcome, and it is worth mirroring the same assertion in any in-process NetworkX path, which will not check.

Why a negative edge breaks Dijkstra specifically Node C is settled at cost 40 via B. A later-explored edge from D to C carries a negative weight, giving a cheaper path of 34. Dijkstra never revisits a settled node, so the shorter path is never found and the reported route is not shortest. Settled means final — which a negative edge violates A 0 B 25 C settled at 40 D 25 15 20 −11 true shortest to C is 34 via D Dijkstra reports 40 and never looks again No exception, no warning — just a route that is six seconds worse than the one that existed, on some queries and not others. Three sources of non-positive weights A single build produced 1 840 edges from an uncapped regeneration credit, 11 200 from a coefficient entered with the wrong sign, and 46 from float32 underflow on very short edges. Where negative weights come from, across one build regen credit uncapped 1 840 edges cap at 90 % of gross coefficient sign error 11 200 edges raise, do not clip float32 underflow 46 edges compose in float64 Eleven thousand edges is a configuration error — clipping it would have produced a plausible graph from a broken config. Counts of this shape are why the clamp statistics belong in the build report rather than in a debug log nobody reads.

Validation checklist

  • Every weight column is strictly positive. Assert before handing the graph to any solver, and again after any overlay is applied.
  • Clamp counts are logged per build. Track them over time; a step change means a coefficient or a data source moved.
  • Credits never exceed their base. Assert credit <= gross before the subtraction rather than inferring it from the result.
  • A deliberately negative coefficient raises. Feed a negative multiplier and confirm the pipeline stops rather than clipping it into a plausible range.
  • Round-trip cost is symmetric where it should be. On a flat two-way edge, the forward and reverse weights should match. A difference points at a directional term applied with the wrong sign.