SSSP with Negative Edges, in depth: why Dijkstra breaks, a tested Dijkstra-Bellman-Ford hybrid, potentials, scaling and the post-2022 algorithms

Where negative edges come from

Negative weights are rarely physical distances. They appear when edge weights are differences or logarithms. Currency conversion graphs use weight -log(rate), so a profitable loop becomes a negative cycle. Systems of difference constraints, x_v - x_u <= w, become shortest-path problems where a negative cycle means the constraints are infeasible; schedulers and timing analysers solve them constantly. Min-cost flow algorithms run shortest paths on residual graphs whose reverse edges carry negated costs. Planning problems with rewards subtract rewards from costs. In each case the negative edges carry meaning and cannot simply be clipped.

Why Dijkstra breaks

Dijkstra's correctness rests on one claim: when the vertex with the smallest tentative distance is removed from the heap, no later path can improve it, because every remaining path to it must first reach some vertex with a distance at least as large and then add non-negative weight. A negative edge breaks the "add non-negative weight" step.

The smallest counterexample has three vertices: s to a costs 2, s to b costs 5, b to a costs -4. Dijkstra settles a at 2 before it ever looks at b. The true distance is 5 - 4 = 1. With a visited flag, the error is permanent. Without one (the lazy variant that re-pushes improved vertices), the answer becomes correct but the running time is no longer O(m log n); on adversarial graphs it becomes exponential.

The other tempting fix, adding a constant to every edge to make all weights non-negative, is wrong because it penalises paths by their number of edges. A five-edge path gains five times the constant and a one-edge path gains it once, so the ordering of paths changes. The correct version of that idea is a potential function, which adds a per-vertex amount rather than a per-edge one; it appears below.

Negative cycles change the question

If a cycle with negative total weight is reachable from the source, distances to every vertex reachable from that cycle are minus infinity: go round the loop again and the path gets cheaper. Any algorithm for this problem must therefore do one of two things: compute distances when no reachable negative cycle exists, or report that one does. A cycle that the source cannot reach does not affect the answer and is invisible to source-based algorithms, which is usually what you want. If you need to find every negative cycle in a graph, add a virtual source with zero-weight edges to every vertex.

Termination conditions are where implementations go wrong. A correct algorithm needs a bound on how much work a cycle-free instance can take, and must report a cycle when that bound is passed, rather than looping until a timeout.

The baseline: Bellman-Ford and SPFA

Bellman-Ford relaxes every edge, n - 1 times. After pass i, every distance is at most the length of the best path using at most i edges; since a simple path has at most n - 1 edges, n - 1 passes suffice, and an improvement on pass n proves a negative cycle. Two cheap improvements matter in practice: stop as soon as a pass changes nothing, and only relax edges out of vertices that changed in the previous pass. The second improvement, run with a FIFO queue, is SPFA; its worst case is still O(nm) and adversarial inputs reach it, as the SPFA article shows.

The number of passes Bellman-Ford needs is governed by the hop count of shortest paths, the number of edges on them. On a road network or grid, hop counts are in the hundreds or thousands even when only a handful of edges are negative. That observation suggests a better measure.

A Dijkstra-Bellman-Ford hybrid

Let eta be the largest number of negative edges on any shortest path. On many real inputs eta is tiny even when the hop count is large. The hybrid exploits this: run Dijkstra using only the non-negative edges, then make one pass over negative edges leaving any vertex Dijkstra touched, and repeat with the vertices that improved as the new starting set. Dijkstra is correct with several seeds at arbitrary starting distances, so each round fully propagates improvements along non-negative edges.

import heapq

INF = float("inf")

class NegativeCycle(Exception):
    pass

def sssp_hybrid(n, edges, s):
    """Dijkstra on non-negative edges, one pass over negative edges, repeat."""
    pos = [[] for _ in range(n)]
    neg = [[] for _ in range(n)]
    k = 0
    for u, v, w in edges:
        if w < 0:
            neg[u].append((v, w))
            k += 1
        else:
            pos[u].append((v, w))
    max_rounds = min(k, n - 1) + 1          # a simple path uses each negative edge once
    dist = [INF] * n
    dist[s] = 0
    frontier = {s}
    rounds = 0
    while frontier:
        rounds += 1
        if rounds > max_rounds:
            raise NegativeCycle(f"still improving after {max_rounds} rounds")
        heap = [(dist[v], v) for v in frontier]
        heapq.heapify(heap)
        touched = set()
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue                     # stale heap entry
            touched.add(u)
            for v, w in pos[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
        frontier = set()
        for u in touched:
            for v, w in neg[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    frontier.add(v)
    return dist, rounds

The invariant is the Bellman-Ford one with negative edges counted instead of all edges: after round i, every distance is at most the best path using at most i - 1 negative edges. So the loop ends after at most eta + 1 rounds, each costing one Dijkstra, O(m log n). Without a reachable negative cycle, eta is at most min(k, n - 1) for k negative edges, which gives the cycle test. This is a classical idea; recent near-linear algorithms use a version of it as their base case after first reshaping the graph so that eta is small.

Worked example

Running the code above on this graph, with a small driver that prints the distances and the new frontier at the end of each round, gives:

round 1 {'s': 0, 'a': 3, 'b': 5, 'c': 6, 'd': 3, 't': 10} next frontier ['a', 'd']
round 2 {'s': 0, 'a': 3, 'b': 5, 'c': 5, 'd': 2, 't': 5} next frontier ['d']
round 3 {'s': 0, 'a': 3, 'b': 5, 'c': 5, 'd': 2, 't': 4} next frontier []
rounds 3 bf True

Round 1's Dijkstra finds a = 4, b = 5, c = 6, d = 8 and t = 10 using non-negative edges. The negative pass then improves a to 3 through b and d to 3 through c. Round 2 starts from a and d: c drops to 5 through the better a, t drops to 5 through d, and the negative pass improves d again, to 2. Round 3 propagates d = 2 to t = 4 and nothing further improves. The shortest path uses two negative edges, eta = 2, and the loop took eta + 1 = 3 rounds. The last line confirms agreement with Bellman-Ford. The same harness compared both algorithms on 500 random graphs, 221 of them with a reachable negative cycle, and they agreed on all 500.

Measured against Bellman-Ford

On graphs whose shortest paths have few hops, early-exit Bellman-Ford converges in a handful of passes and the hybrid has nothing to win. On a random graph with 20,000 vertices and 100,000 edges both finished in about 0.1 seconds in CPython. Grids are different: hop counts are large. These are measured times for a 150 by 150 grid with shuffled edge order, on one laptop:

The hybrid's cost tracks eta, not hop count, and degrades smoothly as negative edges become common. If most edges are negative, Bellman-Ford or SPFA is simpler and comparable.

Special structure first

Before any general algorithm, check for structure that makes the problem easy.

• DAGs. With no cycles at all, process vertices in topological order and relax each edge once: O(n + m), negative weights welcome. Many scheduling and critical-path graphs are DAGs.
• Known potentials. If you have a function phi with w(u, v) + phi(u) - phi(v) >= 0 for every edge, run Dijkstra on the reweighted edges and recover d(v) = d'(v) - phi(s) + phi(v). Each path's length shifts by the same phi(s) - phi(target), so the ordering of paths is preserved. Johnson's algorithm computes phi once with Bellman-Ford and reuses it for all sources; see Johnson's algorithm. In min-cost flow, the previous round's distances are a valid potential, which is why successive shortest paths only needs Bellman-Ford once.
• Small integer weights. Goldberg's 1995 scaling algorithm runs in O(m sqrt(n) log N), where N bounds the absolute value of the most negative weight. It processes weights one bit at a time, maintaining a potential that makes the current approximation non-negative. Its bound depends on N, so it is weakly polynomial, not strongly polynomial.

The research frontier

For decades nothing beat O(nm) for general real weights or Goldberg's bound for integer weights. That changed quickly.

The integer-weight algorithms combine scaling, low-diameter decompositions that cut the graph into pieces with few negative edges per path, and recursively built potentials, finishing with a Dijkstra-Bellman-Ford hybrid like the one above. The real-weight results instead work on vertices with negative out-edges, neutralising them in batches with potentials. None of these is a practical drop-in today: polylogarithmic factors and randomisation make them slower than the hybrid or SPFA on realistic sizes. Their value for practitioners is the shape of the idea: reduce eta, then let Dijkstra do the work.

Failure modes

• Relaxing from infinity. INF + (-3) is still infinity with floats, but with integer sentinels like 10**18 a negative edge out of an unreached vertex produces a finite garbage distance. Never relax from an unreached vertex.
• Visited flags with negative edges. Copying a standard Dijkstra into the hybrid with a settled flag that persists across rounds silently freezes wrong values. Use the stale-entry check instead.
• Floating-point cycles. With -log(rate) weights, rounding error can make a zero-weight cycle look slightly negative. Use a tolerance or exact rationals for arbitrage detection.
• No cycle bound. Loops that run until nothing changes never stop on a negative cycle. Always cap rounds or passes and raise.
• Reporting the wrong vertices. A cycle makes every vertex reachable from it minus infinity, not just the cycle members. Propagate the flag forward.

Choosing an algorithm

What to do next

1. Find where your negative weights come from and check whether the graph is a DAG.
2. Look for a natural potential: previous-round distances, heuristic bounds or a Johnson pre-pass.
3. Measure eta on real instances by counting negative edges on computed shortest paths.
4. If eta is small, adopt the hybrid above and keep Bellman-Ford as a test oracle.
5. Cap rounds at min(k, n - 1) + 1 and propagate minus infinity from any detected cycle.
6. Fuzz both implementations on random graphs built from potentials, plus planted negative cycles.