Bellman-Ford Algorithm: Shortest Paths with Negative Weights

Learn the Bellman-Ford algorithm for single-source shortest paths including negative edge weights and negative cycle detection.

published: April 7, 2026 reading time: 23 min read author: GeekWorkBench

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

False positive negative cycle detection: If vertices are numbered inconsistently or graph is disconnected, ensure you’re only checking edges reachable from source
Integer overflow: With very negative weights and many edges, distances can underflow; use a bounded range or arbitrary precision integers
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

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

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

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

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

If an attacker can add edges to the graph, they can inject negative-weight edges. This could make the shortest path calculations produce unexpectedly low (or negative) distances, potentially bypassing security constraints that rely on path length validation.

Fix: Validate edge weights before running Bellman-Ford. Reject or cap negative weights if they violate your application’s constraints. Log when negative weights are encountered for security analysis.

Negative cycle infinite loop

When a negative cycle exists in the graph and the implementation doesn’t properly detect it, the algorithm can loop indefinitely or produce distances that decrease unboundedly with each iteration.

Fix: Always run the V-th relaxation iteration to detect negative cycles. Set a maximum iteration count as a safeguard. If a negative cycle is detected, abort and report the cycle existence.

Specially crafted graphs for DoS

An attacker who can control graph topology can craft a graph with many vertices but few edges (or vice versa) that causes O(VE) performance in the worst case, consuming CPU time.

Fix: Set maximum limits on vertex and edge counts before running Bellman-Ford. Set time budgets per iteration and abort if exceeded.

Interview Questions

1. Why do we relax all edges V-1 times in Bellman-Ford?

Any simple path (without cycles) between two vertices has at most V-1 edges. By relaxing all edges V-1 times, we ensure we've considered all possible simple paths. After V-1 iterations, if we can still relax an edge, the path to the destination must include a cycle—and that cycle must be negative (since we already considered all simple paths).

2. What's the difference between a negative cycle and a negative edge?

A negative edge is simply an edge with negative weight—Bellman-Ford handles this fine. A negative cycle is a cycle where the sum of edge weights is negative. If you can reach a negative cycle from your source, you can traverse it arbitrarily many times, making the shortest path undefined (goes to negative infinity). Bellman-Ford detects this on iteration V.

3. When would you choose Bellman-Ford over Dijkstra?

Choose Bellman-Ford when you have negative edge weights OR need negative cycle detection. Choose Dijkstra when all weights are non-negative and you need better performance. In practice, if you're unsure about weight signs and the graph isn't huge, Bellman-Ford's guarantee of correctness makes it a safe default.

4. How can you find which vertices are affected by a negative cycle?

Run Bellman-Ford once to detect the negative cycle, then run it again from any vertex that can reach the negative cycle. Alternatively, after the V-th relaxation that detects the cycle, perform one more pass from all vertices that were relaxed on that pass—they're all part of or reachable from the negative cycle. This is useful for understanding which shortest paths are invalid.

5. What is the time and space complexity of the Bellman-Ford algorithm?

The time complexity is O(V·E), where V is the number of vertices and E is the number of edges. This is because the algorithm performs V−1 iterations, each relaxing all E edges, plus one extra iteration for negative cycle detection. The space complexity is O(V) for storing distances and predecessors, or O(V+E) if the graph is stored as an adjacency list. This makes Bellman-Ford slower than Dijkstra (O((V+E) log V)) but more general in handling negative weights.

6. How does SPFA differ from Bellman-Ford and when is it preferred?

SPFA (Shortest Path Faster Algorithm) is a queue-based variant that only relaxes edges from vertices whose distance has changed, rather than blindly relaxing all edges each iteration. Key differences:

Average-case performance: SPFA is typically O(E) on random graphs vs. Bellman-Ford's guaranteed O(VE).
Worst-case: SPFA can degrade to O(VE) or worse on adversarial graphs.
Negative cycle detection: SPFA detects cycles when a vertex is dequeued V+1 times.
Prefer SPFA when average performance matters more than worst-case guarantees — common in practical routing and scheduling applications.

7. Can Bellman-Ford handle undirected graphs with negative edge weights?

Yes, but with a critical caveat. In an undirected graph, each undirected edge with negative weight effectively forms a 2-edge negative cycle (traversing the edge back and forth). This means a single negative-weight undirected edge already creates a negative cycle with total weight 2w. Bellman-Ford will detect this and report that shortest paths are undefined. To handle this correctly:

Convert each undirected edge into two directed edges (both directions) with the same weight.
Run Bellman-Ford — it will correctly detect the implied negative 2-cycle.
If you need shortest paths on undirected graphs with negative weights, consider reformulating the problem or using alternative algorithms like Johnson's.

8. How would you modify Bellman-Ford to output the actual vertices forming a negative cycle?

To extract the negative cycle vertices, track predecessors during relaxation. After the V-th iteration detects a relaxing edge (u, v), follow these steps:

Record the vertex v that was still relaxable on iteration V.
Walk backwards through predecessor pointers V times to guarantee entering the cycle.
Record all vertices visited until you encounter a previously seen vertex — that closed walk is the negative cycle.

This works because the predecessor graph after V iterations must contain a cycle if negative cycle exists, and walking V steps from any relaxable vertex guarantees entry into that cycle.

9. What practical real-world applications use the Bellman-Ford algorithm?

Bellman-Ford appears in several important real-world systems:

Routing Information Protocol (RIP) — A distance-vector routing protocol used in small to medium-sized networks. Routers exchange distance vectors periodically, and Bellman-Ford computes the shortest paths.
Currency arbitrage detection — Financial systems model exchange rates as a graph and use Bellman-Ford to detect negative cycles (arbitrage opportunities) where a sequence of trades yields profit.
Difference constraint solving — Compilers, scheduling systems, and VLSI CAD tools solve systems of difference constraints by converting them to shortest-path problems.
Minimum-cost flow — Successive shortest augmenting path algorithms for min-cost max-flow use Bellman-Ford (or SPFA) to handle negative edge costs in residual networks.

10. How can you optimize Bellman-Ford with early termination for better performance?

The most effective optimization is Yen's early termination — track whether any distance was updated during a full relaxation pass. If no changes occur in an iteration, the algorithm has converged and can stop early:

Detection: Set a boolean flag updated = False at the start of each iteration. Set it to True when any edge relaxes. After the pass, if updated is still False, break early.
Impact: On graphs where shortest paths stabilize quickly, this reduces iterations from V−1 to far fewer — often just 2-5 iterations for real-world road networks.
Caveat: You must still run the V-th iteration to reliably detect negative cycles if early termination didn't occur.

11. Explain the relationship between Bellman-Ford and dynamic programming.

Bellman-Ford is fundamentally a dynamic programming algorithm. The key insight is that the shortest path with at most k edges can be computed from the shortest path with at most k-1 edges:

State: dist_k[v] = shortest path to vertex v using at most k edges
Recurrence: dist_k[v] = min(dist_{k-1}[v], min_{(u,v) in E} dist_{k-1}[u] + w(u,v))
Base case: dist_0[source] = 0, all others = infinity
Termination: After V-1 iterations, all simple paths (≤V-1 edges) are considered. Any further improvement indicates a negative cycle.

This DP formulation explains why the algorithm works and how it relates to other DP techniques like the Viterbi algorithm.

12. What happens if the source vertex cannot reach all other vertices in the graph?

Bellman-Ford handles disconnected components gracefully:

Unreachable vertices: Their distance remains float('inf') throughout execution.
No relaxation: Since dist[u] = inf for unreachable predecessors, the condition dist[u] + weight < dist[v] is never true for unreachable v.
Negative cycles: Only reachable negative cycles are detected. A negative cycle in a disconnected component not reachable from the source has no effect on the algorithm's result.
Path reconstruction: If reconstructing paths, check dist[target] == float('inf') to identify unreachable destinations.

This makes Bellman-Ford suitable for graphs with multiple disconnected components as long as you only care about reachability from the source.

13. How would you modify Bellman-Ford to find the k-th shortest path?

Finding k-th shortest paths requires modifications:

Yen's algorithm: The classic approach uses Bellman-Ford to find the shortest path, then "deviates" from it to find subsequent paths.
Eppstein's algorithm: Faster O(m + k log n) method that precomputes detour edges and uses a priority queue.
Modified relaxation: Store up to k distances per vertex instead of 1. After each iteration, each vertex maintains a sorted list of the k best distances found so far.
Complexity: With k shortest paths per vertex, the complexity becomes O(k·V·E) for the basic approach.

For small k values, Eppstein's algorithm provides excellent practical performance while the simple modification is easier to implement for educational purposes.

14. Can Bellman-Ford be parallelized, and if so, how?

Yes, Bellman-Ford has several parallelization strategies:

Edge-level parallelism: All edges can be processed simultaneously in a single relaxation pass since edge relaxations are independent when reading from the distance array.
Synchronous iteration: Each iteration must complete before the next starts (need consistent dist state), but all edges within an iteration are embarrassingly parallel.
Delta-stepping: A hybrid approach where edges are grouped by weight range and processed in "deltas" — combines Bellman-Ford's ability to handle negative weights with Dijkstra's locality benefits.
GPU acceleration: The regular edge relaxation pattern maps well to GPU architectures — thousands of threads can process different edges simultaneously.
Sparse graphs: The main challenge is load balancing when edges per vertex vary significantly, but CSR (Compressed Sparse Row) format enables efficient batch processing.

15. What is the "potential function" concept in Bellman-Ford, and how does Johnson's algorithm use it?

A potential function (or "reweighting function") transforms edge weights while preserving shortest path relationships:

Definition: A function h(v) such that for every edge (u,v) with weight w, the reweighted weight w' = w + h(u) - h(v) is non-negative.
Property: If h is derived from valid shortest path distances (or any "feasible" potential), shortest paths are identical in both original and reweighted graphs.
Johnson's algorithm: Runs Bellman-Ford once from a dummy vertex to compute potentials h(v) for all vertices, then reweights all edges. Since all w' ≥ 0, Dijkstra can be run from every vertex — achieving O(V² log V + VE) for all-pairs shortest paths.

The potential concept is fundamental to understanding how reweighting transformations preserve optimal substructure while changing absolute values.

16. How does Bellman-Ford handle edge weight updates in a dynamic graph?

For dynamic graphs with changing edge weights, Bellman-Ford can be incrementally updated:

Batch updates: If edge weights change, run Bellman-Ford from scratch. If only a few edges changed, partial re-computation may be faster.
Single edge update: If one edge (u,v) weight changes, re-run relaxation starting from u (or v if directed). The affected region is the set of vertices whose shortest path might change.
SPFA for incremental updates: Since SPFA only processes vertices whose distances changed, it's naturally incremental — re-enqueue vertices affected by the weight change.
Negative cycle handling: If a weight change introduces a negative cycle, Bellman-Ford's V-th iteration will detect it. SPFA can detect cycles by counting vertex dequeuings (V+1 times indicates a cycle).
Leverage locality: If only local edges changed, SPFA's queue-based approach may converge faster than full re-computation.

17. Compare Bellman-Ford's memory usage with Dijkstra's and explain why.

Both algorithms have similar memory complexity, but the patterns differ:

Bellman-Ford: O(V + E) — distance array (V), predecessor array (V), edge list (E if stored explicitly). Can operate on streaming edges without storing the full graph.
Dijkstra with binary heap: O(V + E) — distance array, predecessor array, priority queue (E entries in worst case).
Dijkstra with Fibonacci heap: O(V) for queue since decrease-key is O(1), but implementation complexity is higher.
Trade-off: Bellman-Ford can process edges one at a time (memory-efficient for huge graphs), while Dijkstra requires random access to vertex neighbors (needs adjacency structure).

For extremely sparse graphs with millions of edges, Bellman-Ford's edge-streaming capability is advantageous — you never need to hold all edges in memory simultaneously.

18. What is the difference between "reachable" and "affected" vertices in negative cycle detection?

Understanding this distinction is crucial for proper negative cycle handling:

Reachable from source: Vertices on a path from source to any vertex in the negative cycle. Only these contribute to undefined shortest paths from the given source.
Affected by negative cycle: Vertices reachable from the negative cycle (not just on paths to it). If vertex B is reachable from cycle vertex C, then dist[B] also becomes undefined.
Detection method: After detecting a relaxing edge (u,v) on V-th iteration, walk backwards V times from v using predecessor pointers. The cycle found is the negative cycle. Then BFS/DFS from all cycle vertices identifies all affected vertices.
Why it matters: Only vertices reachable from the negative cycle have undefined distances. Vertices in disconnected components are unaffected even if their weights seem strange.

19. How would you implement Bellman-Ford to handle very large distance values without overflow?

Integer overflow is a real concern with Bellman-Ford on large graphs:

Bounded distances: Use a sentinel value like INT_MIN/2 instead of float('inf') to avoid mixed type handling. Check for overflow on each addition.
Arbitrary precision: Use libraries like Python's decimal or C++'s boost::multiprecision for theoretically unbounded values.
Offset approach: Choose a large offset value M where all real distances are in [0, M]. Use INT_MAX - M as infinity. When adding, check if result would exceed INT_MAX.
Modular arithmetic: For certain applications (like routing with TTL), use modular distance tracking and detect "wraparound" as a negative cycle equivalent.
Detect overflow: After dist[u] + weight, check if the result has a different sign than expected or exceeds preset bounds.

In production systems, prefer the bounded approach with careful validation at input boundaries — this catches malicious graphs while keeping performance reasonable.

20. Design a system that uses Bellman-Ford to detect currency arbitrage opportunities in real-time trading.

Currency arbitrage detection is a classic Bellman-Ford application:

Graph construction: Vertices = currencies. Edge (i,j) with weight = -log(exchange_rate_ij). Negative edge = favorable conversion.
Why -log: Multiplying exchange rates becomes adding negative log rates. A cycle with negative total weight = profitable round-trip.
Detection: Add a dummy vertex connected to all currencies with 0-weight edges. Run Bellman-Ford from dummy. If any edge relaxes on V-th iteration, a negative cycle (arbitrage) exists.
Finding the cycle: After detection, trace back predecessors V times from the relaxable vertex to enter the cycle, then collect vertices until repeat.
Real-time considerations: Exchange rates change constantly. Use SPFA variant for incremental updates, with a maximum iteration budget. If arbitrage disappears (rates shift), detect convergence to re-stabilize.
Implementation: Precompute log(rate) once per update, run Bellman-Ford, use early termination to abort when no further improvement.

This pattern extends to any scenario where you want to detect any "loop" with net negative cost — logistics, scheduling with negative penalties, etc.

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.

Bellman-Ford Algorithm: Shortest Paths with Negative Weights

Introduction

The Algorithm

Handling Negative Cycles

When to Use Bellman-Ford

Trade-off Analysis

Production Failure Scenarios

SPFA: Practical Improvement

Quick Recap Checklist

Observability Checklist

Core Metrics

Health Signals

Alerting Thresholds

Distributed Tracing

Security Notes

Graph poisoning with negative weights

Negative cycle infinite loop

Specially crafted graphs for DoS

Interview Questions

Further Reading

Books & Classic References

Variants & Optimizations

Related Algorithms

Practical Applications

Conclusion

Category

Tags

Related Posts

Dijkstra's Algorithm: Finding Shortest Paths in Weighted Graphs

Floyd-Warshall Algorithm: All-Pairs Shortest Paths

AVL Trees: Self-Balancing Binary Search Trees