Bellman-Ford Algorithm: Shortest Paths with Negative Weights

When graphs contain edges with negative weights, Dijkstra’s algorithm breaks down—and that’s where Bellman-Ford steps in. Originally published in 1958 by Richard Bellman and Lester Ford Jr., this algorithm handles negative weights gracefully while also detecting negative cycles that could make shortest paths undefined (infinitely negative).

The key insight behind Bellman-Ford is surprisingly simple: after V-1 iterations of relaxing all edges, we’ve considered all possible paths up to V-1 edges. If we can still relax an edge on the V-th iteration, a negative cycle exists that can be traversed indefinitely to get arbitrarily low distances.

Introduction

When graphs contain edges with negative weights, Dijkstra’s algorithm fails—a shorter path can always be found after a vertex is processed, breaking the greedy choice. Bellman-Ford handles this scenario correctly by considering all possible paths: after V-1 iterations of relaxing all edges, every path with at most V-1 edges has been examined. If a V-th relaxation is still possible, a negative cycle exists that can be traversed arbitrarily many times, making shortest paths undefined (infinitely negative).

The V-1 iteration bound comes from a simple insight: any simple path (without cycles) between two vertices contains at most V-1 edges. By relaxing all edges V-1 times, we consider all possible simple paths. If we can still improve a distance on iteration V, the improvement must involve a cycle—and that cycle must have negative total weight. This negative cycle detection capability distinguishes Bellman-Ford from Dijkstra and makes it essential for systems where negative weights can appear, such as currency arbitrage detection, cost adjustment networks, or routing protocols with negative latency costs.

Bellman-Ford runs in O(VE) time, which is slower than Dijkstra’s O((V + E) log V), but guarantees correctness with any edge weights. Practical variants like SPFA (Shortest Path Faster Algorithm) often perform much better in practice by only relaxing edges from vertices whose distance changed. Understanding Bellman-Ford means understanding the dynamic programming foundation underlying it, how to reconstruct paths and detect negative cycles, and when to choose it over faster alternatives. It’s the algorithm you reach for when correctness matters more than speed, especially in adversarial or untrusted graph inputs.

The Algorithm

def bellman_ford(graph, source):
    """
    Bellman-Ford single-source shortest paths.

    Args:
        graph: List of edges [(u, v, weight)] or dict for adjacency list
        source: Source vertex

    Returns:
        (distances, has_negative_cycle) tuple
        distances dict is empty if negative cycle detected
    """
    # Build edge list from graph
    vertices = set()
    edges = []

    if isinstance(graph, dict):
        for u in graph:
            vertices.add(u)
            for v, weight in graph[u]:
                vertices.add(v)
                edges.append((u, v, weight))
    else:
        # Assume list of edges
        for u, v, weight in graph:
            vertices.add(u)
            vertices.add(v)
            edges.append((u, v, weight))

    # Initialize distances
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0

    # Relax all edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight

    # Check for negative cycle on V-th iteration
    has_negative_cycle = False
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            has_negative_cycle = True
            dist = {}  # Indicate undefined distances
            break

    return dist, has_negative_cycle

Handling Negative Cycles

When a negative cycle is reachable from the source, shortest paths are undefined—you can loop the cycle infinitely to get arbitrarily low costs. Bellman-Ford detects this on the V-th iteration:

def bellman_ford_with_path_reconstruction(graph, source, target):
    """Returns (distance, path, has_negative_cycle)."""
    # ... same initialization as above ...

    # Track predecessors for path reconstruction
    pred = {v: None for v in vertices}

    # Relax all edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u

    # Check for negative cycle
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            return None, None, True  # Negative cycle exists

    # Reconstruct path
    if dist[target] == float('inf'):
        return float('inf'), [], False

    path = []
    current = target
    while current is not None:
        path.append(current)
        current = pred[current]

    return dist[target], path[::-1], False

When to Use Bellman-Ford

Use Bellman-Ford when:

• Graph has negative edge weights
• You need to detect negative cycles
• V is small relative to E (sparse graphs)
• You need guaranteed correctness with any edge weights

Don’t use Bellman-Ford when:

• All weights are non-negative (use Dijkstra for better performance)
• Graph is very large with many vertices (O(VE) may be too slow)
• You need all-pairs shortest paths (use Floyd-Warshall)

Trade-off Analysis

Aspect	Bellman-Ford	Dijkstra	Floyd-Warshall
Negative Weights	Yes	No	Yes
Negative Cycle Detection	Yes	No	Yes
Time (Sparse)	O(VE)	O((V+E) log V)	O(V³)
Time (Dense)	O(VE)	O(V²)	O(V³)
Single Source	Yes	Yes	Yes (all pairs)

Production Failure Scenarios

1. False positive negative cycle detection: If vertices are numbered inconsistently or graph is disconnected, ensure you’re only checking edges reachable from source
2. Integer overflow: With very negative weights and many edges, distances can underflow; use a bounded range or arbitrary precision integers
3. Large graphs: O(VE) becomes prohibitive for graphs with millions of edges—consider SPFA (Shortest Path Faster Algorithm) as a practical variant

SPFA: Practical Improvement

In practice, the Queue-based SPFA algorithm often performs much better than pure Bellman-Ford:

from collections import deque

def spfa(graph, source):
    """Shortest Path Faster Algorithm (SPFA) - queue-based Bellman-Ford."""
    vertices = set()
    edges = []

    if isinstance(graph, dict):
        for u in graph:
            vertices.add(u)
            for v, weight in graph[u]:
                vertices.add(v)
                edges.append((u, v, weight))

    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    in_queue = {v: False for v in vertices}
    queue = deque([source])
    in_queue[source] = True

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, weight in graph.get(u, []):
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True

    return dist

Quick Recap Checklist

• Initialize all distances to infinity except source (0)
• Relax all edges exactly V-1 times
• On V-th iteration, check for further relaxation to detect negative cycles
• Reconstruct paths using predecessor tracking
• Use SPFA variant for better average performance
• Remember: negative cycles make shortest paths undefined

Observability Checklist

Track Bellman-Ford implementations to catch convergence and negative cycle issues.

Core Metrics

These four metrics form the baseline for monitoring any Bellman-Ford implementation in production. Relaxation count tracks how many edge relaxation passes the algorithm performed — in a graph without negative cycles, this should equal V-1 once the shortest paths have stabilized. If your implementation supports early termination (stopping when a full pass produces no updates), relaxation count also tells you how many passes were actually needed versus the theoretical maximum.

Shortest distance convergence per vertex is the most granular view of progress: each vertex should see its distance value decrease monotonically until it reaches its final shortest-path value. Monitoring this per-vertex lets you spot vertices whose distances plateau prematurely (indicating a bug) or keep changing (hinting at an unresolved negative cycle). In SPFA, this metric also reflects how effectively the queue is distributing work — if only a few vertices update frequently while most stay static, the queue discipline is working as intended.

The negative cycle detection result is a boolean flag set on the V-th relaxation pass: if any edge can still be relaxed, a negative cycle exists and the algorithm should abort. This is the single most important correctness signal — treat it as a pass/fail rather than a scalar value. The queue size metric is SPFA-specific and serves as a performance proxy: a queue that drains quickly indicates fast convergence, while a queue that grows large or fluctuates wildly suggests the graph structure is adversarial to SPFA’s queue discipline.

• Relaxation count (should be V-1 iterations for acyclic shortest paths)
• Shortest distance convergence per vertex
• Negative cycle detection result (edge still relaxing on V-th pass)
• Queue size for SPFA variant

Health Signals

Health signals are runtime patterns that tell you whether a Bellman-Ford run is healthy, degrading, or in a failure state. Unlike core metrics, which log raw values, health signals are boolean or categorical flags that you can route directly to alerting systems. They bridge the gap between “I have a number” and “something is wrong.”

A relaxation count exceeding V-1 is the clearest negative cycle indicator — it means the algorithm could not converge within the theoretical maximum for simple paths, which only happens when a negative cycle keeps providing shorter and shorter paths. Distances not converging within the expected iteration count is a softer signal: it might indicate a negative cycle, but it could also mean your implementation has a bug or your graph has an unexpected structure. The distinction matters because a negative cycle requires algorithm-level handling, while a bug requires a code fix. Queue size growing unbounded in SPFA is a performance degradation signal — SPFA can degrade to O(VE) on adversarial graphs, and an unbounded queue is the warning sign. Finally, distance values trending toward negative infinity are a definitive negative cycle indicator in a different form: if distances keep decreasing pass after pass without bound, the algorithm is chasing a cycle that yields arbitrarily low costs.

• Relaxation count exceeding V-1 (potential negative cycle)
• Distances not converging within expected iterations
• Queue size growing unbounded (SPFA performance degradation)
• Distance values going to negative infinity (negative cycle indicator)

Alerting Thresholds

Alerting thresholds convert health signals into actionable alerts. The key principle is that Bellman-Ford’s theoretical guarantees give you precise, algorithm-derived thresholds — use them. Arbitrary thresholds (like “alert if runtime > 1 second”) are less useful because they vary with graph size and hardware. The thresholds below are derived from first principles and apply universally.

An edge relaxing on the V-th iteration is the definitive negative cycle detection event. Unlike softer signals, this one is mathematically guaranteed: if you reach iteration V and can still relax an edge, a negative cycle exists. Alert immediately on this condition — do not wait, do not retry. The iteration count > V+5 threshold is a secondary safeguard for negative cycle detection and also catches implementation bugs. Bellman-Ford should always converge by V-1 in a graph without negative cycles; exceeding V+5 iterations is strong evidence of a problem even if the V-th pass check somehow missed it. Distance values trending to negative infinity are another negative cycle signature: in a normal run, distances approach their shortest-path values and stop changing. If they keep decreasing without bound, the algorithm is caught in a cycle. For SPFA, a queue size exceeding 3V is the performance degradation threshold. SPFA’s queue should be small relative to V in practice; a queue larger than three times the vertex count indicates the graph structure is working against the algorithm’s locality advantages.

• Edge relaxes on V-th iteration: negative cycle detected, alert immediately
• Iteration count > V+5: likely negative cycle or implementation bug
• Distance values trending to -infinity: negative cycle, alert
• SPFA queue size > 3V: performance problem, investigate

Distributed Tracing

When Bellman-Ford runs as part of a distributed system — for example, in a routing service, a currency arbitrage detector, or a scheduling optimizer — instrumenting it with distributed tracing turns a black-box algorithm into a transparent component. The goal is to make every Bellman-Ford invocation observable in the context of the larger request that triggered it.

The core tracing signal is iteration count paired with per-vertex relaxation counts. Iteration count tells you how many full edge-relaxation passes executed; per-vertex relaxation counts reveal which parts of the graph are driving convergence. A vertex that gets relaxed many times while others relax few times indicates an asymmetric graph structure — useful diagnostic information when debugging unexpected performance. Always include vertex count and edge count as span attributes: these are the primary determinants of workload size, and correlating them with actual wall-clock time lets you build a performance model for your specific graph distributions.

The VE metric is the key performance indicator for Bellman-Ford complexity. A trace that captures wall-clock time per iteration lets you compute effective VE operations per second. If this rate degrades significantly across runs on similarly-sized graphs, the graph topology may have changed — a dense or adversarial graph structure is driving the algorithm toward its worst case. Correlating slow runs with high V*E counts is the most direct way to distinguish algorithmic slowness from hardware or network slowness.

• Trace Bellman-Ford with iteration count and vertex relaxation counts
• Include edge count and vertex count in span attributes
• Correlate slow runs with large V*E operations

Security Notes

Bellman-Ford has specific security concerns.

Graph poisoning with negative weights

Bellman-Ford handles negative weights correctly, but that capability becomes a liability when graph input is untrusted. An attacker who injects negative-weight edges can drive shortest path distances to arbitrarily low values, potentially bypassing authentication checks, credit limits, or other constraints that rely on path cost validation.

Many applications use path length as a proxy for something else—computational cost, monetary value, risk score. If the algorithm produces a negative distance, downstream logic may interpret it as a credit rather than a debt, or a benefit rather than a cost.

Mitigation checklist:

• Validate all edge weights against application-specific ranges before processing
• Reject negative weights outright if they don’t make sense in your domain
• If negative weights are legitimate (e.g., financial arbitrage), treat the resulting paths as suspicious by default
• Log every negative weight detection with full edge context for security review
• Consider capping minimum distances to prevent integer underflow in downstream arithmetic

Negative cycle infinite loop

Bellman-Ford’s V-th iteration is not a loop optimization—it is a correctness requirement. If your implementation skips it, or if a bug causes early termination, you lose negative cycle detection entirely. The algorithm will keep relaxing edges indefinitely because the negative cycle provides an infinite supply of shorter paths.

A missing V-th iteration check can cause your service to hang. The relaxation count grows without bound, distances keep decreasing, and the calling process waits for an answer that never stabilizes. For integer-based distance representations, values may also underflow and wrap around, producing positive distances from negative ones.

Mitigation checklist:

• Always execute the V-th relaxation iteration even after the main loop completes
• If any edge relaxes on iteration V, treat it as a negative cycle detection and abort
• Set an explicit maximum iteration count as a secondary safeguard (e.g., V + 5)
• Monitor iteration count in production and alert if it approaches the limit
• Use a bounded distance representation (e.g., sentinel values) to catch underflow

Specially crafted graphs for DoS

Bellman-Ford’s O(VE) complexity is dominated by the product of vertices and edges. An attacker who can specify graph topology can exploit this by crafting inputs that maximize VE—a graph with V=10,000 and E=10,000 still gives100 million relaxation operations, but V=100,000 with E=1,000 produces the same result with a fraction of the memory footprint, making the attack harder to detect.

The worst-case trigger is a dense graph with many vertices but strategically placed edges that prevent early termination. Bellman-Ford processes all V-1 iterations regardless of whether distances have converged, unlike SPFA which can converge early.

Mitigation checklist:

• Set hard limits on vertex count (e.g., max 50,000) and edge count (e.g., max 500,000)
• Set a time budget per iteration and abort if the V-1 iteration loop exceeds it
• Use SPFA with its own iteration limit as a practical alternative (it often converges before V-1 iterations)
• Monitor per-iteration time and alert if iteration duration grows superlinearly
• For API-facing graph inputs, consider queueing large requests rather than rejecting them outright

Interview Questions

Further Reading

Books & Classic References

• “Introduction to Algorithms” (CLRS), 4th Ed. – Chapter 22: Single-Source Shortest Paths. The gold-standard textbook treatment with proofs of correctness, negative cycle detection, and the relationship to difference constraints.
• “Algorithm Design” by Kleinberg & Tardos – Chapter 6: Dynamic Programming. Presents Bellman-Ford as a dynamic programming algorithm that iteratively computes shortest paths with at most k edges.
• Richard Bellman (1958) – “On a routing problem” in Quarterly of Applied Mathematics, 16(1), 87–90. The original paper introducing the algorithm.
• L. R. Ford Jr. (1956) – “Network Flow Theory”, RAND Corporation Paper P-923. Ford’s independent formulation of the same algorithm.

Variants & Optimizations

• SPFA (Shortest Path Faster Algorithm) – Queue-based variant with typical-case O(E) performance. Uses a FIFO queue to avoid unnecessary relaxations. Particularly effective on sparse graphs.
• Yen’s Optimization – Early termination: stop iterating if no distances change during a full pass. Drastically improves real-world performance, especially when the shortest path tree stabilizes quickly.
• Bannister & Eppstein (2012) – Randomized edge relaxation ordering that achieves expected O(V*E) worst-case but with better constants.
• Delta-Stepping – A parallel variant that divides edges by weight range, combining ideas from Dijkstra and Bellman-Ford for multi-core architectures.

Related Algorithms

• Dijkstra’s Algorithm – O((V+E) log V) but requires non-negative weights. The algorithm of choice when weights are guaranteed non-negative.
• Floyd-Warshall Algorithm – O(V³) all-pairs shortest paths. Handles negative weights and detects negative cycles, but trades off performance for complete pair-wise results.
• Johnson’s Algorithm – Uses Bellman-Ford once to reweight edges (via a potential function), then runs Dijkstra from every vertex. Achieves O(V² log V + VE) for all-pairs shortest paths with negative weights.
• Difference Constraints / Systems of Difference Constraints – Bellman-Ford solves systems of inequalities xⱼ − xᵢ ≤ c by converting them to a graph and running shortest paths. Applications: scheduling, real-time systems, VLSI layout.

Practical Applications

• Distance-Vector Routing (RIP Protocol) – Bellman-Ford is the algorithmic core of the Routing Information Protocol, where routers exchange distance vectors to compute network paths.
• Currency Arbitrage Detection – Transform exchange rates into log-space (negative log of rate), then detect negative cycles — each negative cycle represents an arbitrage opportunity.
• Constraint Satisfaction & Scheduling – Solve difference constraints for job scheduling with minimum/maximum time gaps between tasks.
• Minimum-Cost Flow – Bellman-Ford handles negative edge costs in successive shortest augmenting path algorithms for min-cost max-flow.

---

Conclusion

Bellman-Ford handles graphs where edges have negative weights—something Dijkstra cannot do. The algorithm relaxes all edges V-1 times to find shortest paths, then runs one more iteration to detect negative cycles (if any edge can still be relaxed, a negative cycle exists). Time complexity is O(VE), which is slower than Dijkstra’s O((V+E) log V) but necessary when negative weights or negative cycle detection are requirements. SPFA is a queue-based variant that often performs better in practice. When all weights are non-negative, prefer Dijkstra for speed. When you need guaranteed correctness with arbitrary weights or must detect negative cycles, Bellman-Ford is the safe choice.