Bellman-Ford Algorithm — When Dijkstra Fails

Most graph shortest-path problems on LeetCode are solved with Dijkstra's algorithm. It is fast, well-understood, and works beautifully for the majority of cases you will encounter. But Dijkstra has a critical blind spot: it breaks down completely when the graph contains negative edge weights. When an interviewer hands you a graph problem with negative costs, flight prices that can be discounted below zero, or currency exchange rates that can represent arbitrage opportunities, Dijkstra will give you the wrong answer — silently, confidently, incorrectly.

Bellman-Ford fills exactly that gap. It is the classical single-source shortest path algorithm that handles negative edge weights correctly, and it can go one step further: it can detect negative cycles, a property that Dijkstra cannot match. Understanding when to reach for Bellman-Ford instead of Dijkstra is the kind of nuanced graph knowledge that separates strong candidates from average ones in technical interviews.

This guide covers how Bellman-Ford works from first principles, why V-1 iterations are the right number, how the negative cycle check in the Vth iteration works, and which LeetCode problems specifically require or reward Bellman-Ford thinking. The three core problems — Cheapest Flights Within K Stops (#787), Network Delay Time (#743), and Find the City With the Smallest Number of Neighbors (#1334) — are examined in detail.

The algorithm is named after Richard Bellman and Lester Ford Jr., who independently described it in the late 1950s. It predates Dijkstra's algorithm and remains relevant today not because it is the fastest option, but because it is the most general. Bellman-Ford runs in O(V·E) time — significantly slower than Dijkstra's O((V + E) log V) — but it is the only classical algorithm that correctly handles graphs with negative edge weights and can detect negative cycles.

If you have been avoiding Bellman-Ford because it seems complex, this guide will show you that the core idea is actually simpler than Dijkstra's priority queue mechanics. The implementation is a triple-nested structure of: initialize distances, relax all edges V-1 times, then check once more for negative cycles. Once you understand why each step works, the algorithm becomes intuitive rather than memorized.

Dijkstra's algorithm makes a greedy assumption: once a node is marked as 'settled,' its distance is final. This assumption is what makes Dijkstra fast — by always processing the minimum-distance unvisited node first, it can commit to distances early and never revisit them. The correctness proof relies entirely on non-negative edge weights.

The reason non-negative weights are required is subtle. When Dijkstra marks node X as settled with distance d, it is saying: 'No future path through any other unsettled node can produce a shorter route to X.' This is only true when all edges are non-negative. If edge weights can be negative, a future node Y with distance d+5 could have an edge to X with weight -10, producing a total path of d-5 — shorter than d, contradicting the settled assumption.

Consider a concrete counter-example. Nodes A, B, C. Edges: A→B with weight 1, A→C with weight 3, B→C with weight -3. The shortest path from A to C is A→B→C with cost 1 + (-3) = -2. But Dijkstra will settle C immediately when it sees the direct edge A→C with cost 3, before it discovers that going through B produces a better answer. The settled-node assumption fires incorrectly, and Dijkstra returns 3 instead of -2.

This is not a bug in Dijkstra — it is a fundamental limitation of the greedy approach. The algorithm was never designed for negative weights. When interviewers ask about negative-weight graphs, they are testing whether you know this distinction: Dijkstra is faster but requires non-negative weights; Bellman-Ford is slower but handles the general case.

A common interview mistake is attempting to 'fix' Dijkstra for negative weights by adding a constant offset to all edges to make them non-negative. This does not work: adding a constant to each edge changes the total cost of paths by different amounts depending on how many edges each path uses. A path with 3 edges gets a larger offset than a path with 1 edge, distorting the relative ordering of paths. Only the Johnson's algorithm — which reweights edges using shortest path potentials — can validly handle this transformation, and it uses Bellman-Ford as a subroutine to compute those potentials.

Bellman-Ford works by repeatedly relaxing all edges in the graph. Relaxing an edge (u, v, w) means: if the current known distance to u plus the edge weight w is less than the current known distance to v, update the distance to v. This operation is performed for every edge in the graph, and it is repeated V-1 times, where V is the number of vertices.

The intuition for why V-1 iterations suffice is elegant. In a graph with V vertices, the shortest path between any two vertices — assuming no negative cycle — can have at most V-1 edges. A path with more than V-1 edges must revisit at least one vertex, and if it is optimal, that vertex would form a zero-weight cycle, which we can ignore. After iteration k, Bellman-Ford guarantees that all shortest paths using at most k edges have been found. After V-1 iterations, all shortest paths using at most V-1 edges have been found — which covers every possible shortest path.

The initialization sets the distance to the source vertex as 0 and all other distances as infinity. This represents the base case: with zero relaxation iterations, we know only that the source is at distance 0. After the first full pass over all edges, we know the shortest path using at most 1 edge. After the second pass, at most 2 edges. After V-1 passes, all shortest paths.

The key difference from Dijkstra is that Bellman-Ford does not maintain a priority queue or a settled set. Every edge is considered every iteration, regardless of whether the source vertex's distance has been finalized. This redundancy — revisiting edges that have already converged — is what makes Bellman-Ford slower, but also what makes it correct: a negative edge discovered late in the process will still propagate its effect correctly in subsequent iterations.

In practice, the algorithm can be implemented with an early termination optimization: if a full pass over all edges produces no updates, the algorithm has converged and you can stop. In the best case (no negative weights, graph already exploring in BFS order), this can reduce iterations dramatically. In the worst case (a linear chain of vertices), all V-1 iterations are needed.

The pseudocode is intentionally simple: initialize dist[src] = 0, all others = infinity. For i from 1 to V-1: for each edge (u, v, w): if dist[u] + w < dist[v], set dist[v] = dist[u] + w. After the loops, run one more pass over all edges: if any edge still produces an update, a negative cycle exists.

A negative cycle is a cycle in the graph whose total edge weight sum is negative. If a negative cycle is reachable from the source, the shortest path to any vertex reachable from that cycle is negative infinity — you can traverse the cycle repeatedly to decrease the distance without bound. In such graphs, the concept of a 'shortest path' is undefined.

Bellman-Ford detects negative cycles through a simple observation: after V-1 iterations, if the graph has no negative cycle, all distances have converged. If running one more relaxation pass — the Vth iteration — still produces any update, it means there exists a negative cycle. The distance of some vertex can still be decreased, which is only possible if a negative cycle is allowing the path cost to decrease indefinitely.

The negative cycle detection step is straightforward: after completing the V-1 relaxation iterations, run one additional full pass over all edges. If any edge (u, v, w) satisfies dist[u] + w < dist[v], report that a negative cycle exists. The vertex v that gets updated is either on the negative cycle or reachable from it.

Real-world applications of negative cycle detection extend well beyond competitive programming. In currency exchange, a negative cycle corresponds to an arbitrage opportunity: a sequence of currency conversions that returns more than the starting amount. Detecting this is equivalent to detecting a negative cycle in a graph where edge weights are negative logarithms of exchange rates. In network routing, negative cycles in the Bellman-Ford routing protocol (used in RIP — Routing Information Protocol) represent routing loops that cause packets to circulate indefinitely. The 'count to infinity' problem in RIP is a negative cycle pathology.

For LeetCode purposes, negative cycle detection most commonly appears as a question about whether a valid shortest path exists. If the graph has a negative cycle reachable from the source that also reaches the destination, the answer is 'no valid shortest path' or negative infinity. Bellman-Ford gives you both the distances and the cycle detection in a single algorithm pass.

Three LeetCode problems are canonical for Bellman-Ford practice. Each one requires either the K-step variant of Bellman-Ford, demonstrates why Dijkstra needs modification for certain constraints, or uses the distance-minimization pattern in a new context. Solving all three gives you coverage of the core use cases.

Cheapest Flights Within K Stops (#787) is the flagship Bellman-Ford problem on LeetCode. You are given a flight network with prices (always non-negative) and must find the cheapest flight from src to dst using at most K stops (K+1 edges). The K-stop constraint makes this a perfect fit for the Bellman-Ford structure: run exactly K+1 relaxation iterations instead of V-1. After iteration i, you have the cheapest flight using at most i edges. After K+1 iterations, you have the answer. The critical implementation detail: to enforce the 'at most K stops' constraint, copy the distance array at the start of each iteration and only update from the copied values — otherwise a single iteration might chain multiple edge relaxations, using more than one new edge per pass.

Network Delay Time (#743) asks for the minimum time for a signal to reach all nodes from a given source, in a directed weighted graph with positive weights. This is a standard single-source shortest path problem solvable with both Dijkstra and Bellman-Ford. On LeetCode, Dijkstra with a heap is faster and typically preferred. However, working through #743 with Bellman-Ford is valuable for building intuition: initialize source to 0, relax all edges V-1 times, then take the maximum distance among all reachable nodes. If any node remains at infinity, return -1. This is the cleanest possible Bellman-Ford implementation — no K-stop constraint, no negative weights, pure structure.

Find the City With the Smallest Number of Neighbors at a Threshold Distance (#1334) is a Floyd-Warshall problem at its core — it asks for all-pairs shortest paths, not just single-source. But it can be solved by running Bellman-Ford once for each vertex as the source, which gives O(V^2 · E) time. In practice, Floyd-Warshall's O(V^3) is cleaner. The value of solving it with Bellman-Ford is understanding the relationship: Bellman-Ford run from every vertex = all-pairs shortest paths, just less efficiently than Floyd-Warshall.

A fourth problem worth noting: Minimum Cost to Reach Destination in Time (#1928) adds a time budget constraint on top of the shortest path structure. This is solved with a modified Bellman-Ford where the state is (node, time_remaining) rather than just node — a pattern common in graph DP problems where an extra constraint limits the number of edges.

When approaching any LeetCode graph problem, scan for two signals that suggest Bellman-Ford: the presence of negative edge weights, or a constraint on the maximum number of edges (hops) allowed in the path. The first signal requires Bellman-Ford for correctness; the second makes Bellman-Ford's iteration structure naturally encode the constraint.

Choosing the right shortest-path algorithm is a critical interview skill. The decision tree is not complicated, but candidates who have not explicitly studied it tend to default to Dijkstra for everything — which fails on negative-weight inputs and is unnecessarily complex for unweighted inputs.

Dijkstra's algorithm is the right choice when all edge weights are non-negative and you need single-source shortest paths efficiently. With a binary heap, Dijkstra runs in O((V + E) log V). With a Fibonacci heap, O(V log V + E). For dense graphs, Dijkstra with an adjacency matrix runs in O(V^2). Dijkstra is optimal for the non-negative case and should be your default for weighted graph shortest-path problems without negative weights.

Bellman-Ford is the right choice when negative edge weights are present, when you need to detect negative cycles, or when you have a constraint on the maximum number of edges in the path (the K-stops pattern). Bellman-Ford runs in O(V·E), which is significantly slower than Dijkstra for large graphs, but correctness is not negotiable when negative weights are involved.

SPFA (Shortest Path Faster Algorithm) is a queue-based optimization of Bellman-Ford. Instead of relaxing all edges every iteration, SPFA maintains a queue of vertices whose distances have recently been updated and only processes those. In practice, SPFA runs much faster than Bellman-Ford on sparse graphs with few negative edges. However, SPFA has O(V·E) worst-case time complexity — the same as Bellman-Ford — and can be deliberately constructed to degenerate. LeetCode test cases sometimes include SPFA-killing cases. For interview purposes, SPFA is useful to know but not required.

Floyd-Warshall is the right choice when you need all-pairs shortest paths and the graph is small enough (V ≤ 500 typically). It runs in O(V^3) and handles negative weights but not negative cycles. It is three nested loops and is simpler to implement than running Bellman-Ford from every source, but has worse asymptotic complexity for sparse graphs.

The decision framework, summarized: graph has negative cycles to detect → Bellman-Ford; graph has negative weights but no negative cycles and single source → Bellman-Ford; non-negative weights, single source, performance matters → Dijkstra; all-pairs shortest paths, small graph → Floyd-Warshall; unweighted graph → BFS. Knowing this framework and being able to articulate it under interview pressure is what strong graph knowledge looks like.

Bellman-Ford is not the flashiest graph algorithm, and it is not the fastest. But knowing it — really knowing it, not just knowing the name — is a reliable signal of strong graph fundamentals. The candidate who can say 'I would use Bellman-Ford here because negative weights break Dijkstra's greedy assumption, and I need K-1 iterations to enforce the hop constraint' is demonstrating exactly the kind of reasoning that separates senior-level candidates from those who have only surface-level algorithm knowledge.

The core insight to remember: Bellman-Ford's correctness comes from its completeness. Unlike Dijkstra, it does not commit to a result early. It considers every edge, every iteration, allowing negative-weight paths to propagate their improvements across multiple rounds. The price is O(V·E) time, but for graphs with negative weights or K-hop constraints, it is the right price to pay.

Negative cycle detection is the bonus capability. After V-1 iterations have converged, one more pass reveals whether the graph's shortest-path structure is even well-defined. This is used in currency arbitrage detection, routing protocol loop detection, and any domain where cycles of negative cumulative cost represent an exploit or error condition.

The three LeetCode problems to drill are Cheapest Flights Within K Stops (#787), Network Delay Time (#743), and Find the City With the Smallest Number of Neighbors (#1334). Problem #787 is the most important — it combines the K-iteration structure with the per-iteration copy trick, and it is the problem most likely to appear in an interview where Bellman-Ford knowledge is being specifically tested. Solve it cleanly, explain the copy trick, and you have demonstrated mastery.

YeetCode organizes graph problems by algorithm pattern, so you can drill Bellman-Ford problems in sequence alongside Dijkstra and Floyd-Warshall problems. Building fluency in all three and knowing the decision framework for when to use each one is the complete graph shortest-path skill set for technical interviews. Start with #787, move to #743, then round out with #1334 and the decision tree. Bellman-Ford is the algorithm Dijkstra cannot replace — and knowing that makes all the difference.