Bellman-Ford — Single-Source Shortest Path with Negative Edges [LC 787, Google, Amazon]

Problem Statement#

Given a weighted directed graph with n vertices and m edges (weights may be negative) and a source vertex src, find the shortest distance from src to every other vertex. If a negative-weight cycle is reachable from src, report that fact. Use the Bellman-Ford algorithm: repeatedly relax every edge V - 1 times, then perform one more pass to detect negative cycles.

Constraints:

• 1 <= n <= 10^3
• 0 <= m <= 5 * 10^3
• Edge weights in [-10^4, 10^4]
• The graph may be disconnected.

Example:

Input: n = 5, edges = [[0,1,6],[0,2,7],[1,2,8],[1,3,5],[1,4,-4],[2,3,-3],[2,4,9],[3,1,-2],[4,3,7],[4,0,2]], src = 0
Output: dist = [0, 2, 7, 4, -2]
Explanation: 0 -> 2 -> 3 -> 1 -> 4 = 7 + (-3) + (-2) + (-4) = -2.

Why This Problem Matters#

Bellman-Ford is the algorithm Dijkstra cannot replace. Whenever an interview problem mentions negative edge weights, currency arbitrage, or "deal cycles," Bellman-Ford is the right tool. It also forms the relaxation foundation for Johnson's all-pairs algorithm and for distance-vector routing protocols (RIP) used in real-world networking.

LeetCode 787 (Cheapest Flights Within K Stops) is the most-asked variant — it constrains the number of relaxation rounds, which maps perfectly onto Bellman-Ford's V - 1 round structure. Google, Amazon, and Meta interviewers love this problem because a candidate who recognises the "K stops -> K rounds of Bellman-Ford" connection has clearly internalised the algorithm rather than memorised templates.

The negative-cycle detection use case is a classic trick interview question: "Given a list of currency exchange rates, can you make a profit by trading in a cycle?" The reduction is to take -log(rate) as edge weight; a negative cycle means the cycle multiplies your money. Banks, trading firms, and arbitrage detectors quietly rely on this idea.

The Core Insight#

A shortest path in a graph with V vertices uses at most V - 1 edges (otherwise it has a repeated vertex, which means a cycle that we can remove if non-negative or which we cannot avoid if negative).

Bellman-Ford exploits this: initialise dist[src] = 0 and dist[v] = INF for every other vertex. Then for V - 1 iterations, relax every edge. Relaxing edge (u, v, w) means: if dist[u] + w < dist[v], update dist[v] = dist[u] + w and record parent[v] = u.

After V - 1 rounds, dist[v] equals the true shortest distance from src to v for every reachable v — provided there is no negative cycle on the path.

To detect a negative cycle, run one more (the V-th) round. If any edge can still be relaxed, the graph has a negative cycle reachable from src.

A subtle but vital optimisation: if a full round makes no relaxation, you can break early — distances have stabilised. Adding this check turns Bellman-Ford from O(VE) worst case into early-terminating practical performance.

Visual Dry Run#

n = 4, edges: 0->1(1), 1->2(-2), 2->3(3), 0->3(5), src = 0.

Initial: dist = [0, INF, INF, INF].

After 3 rounds (V - 1 = 3) we stop. Final dist = [0, 1, -1, 2].

A 4th round would relax nothing, confirming no negative cycle.

Solution (Optimal)#

Python#

def bellman_ford(n, edges, src):
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    parent = [-1] * n
 
    # V - 1 rounds of relaxing every edge
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                updated = True
        if not updated:
            break  # early termination: no further improvements possible
 
    # V-th round: any further relaxation indicates a negative cycle
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None, None  # negative cycle reachable from src
    return dist, parent

JavaScript#

function bellmanFord(n, edges, src) {
    const INF = Infinity;
    const dist = new Array(n).fill(INF);
    const parent = new Array(n).fill(-1);
    dist[src] = 0;
 
    for (let i = 0; i < n - 1; i++) {
        let updated = false;
        for (const [u, v, w] of edges) {
            if (dist[u] !== INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                updated = true;
            }
        }
        if (!updated) break;
    }
 
    for (const [u, v, w] of edges) {
        if (dist[u] !== INF && dist[u] + w < dist[v]) {
            return { dist: null, parent: null }; // negative cycle
        }
    }
    return { dist, parent };
}

Complexity: Time O(V * E). Space O(V) for the distance and parent arrays. With early termination, real-world performance is often closer to O(E * d) where d is the longest shortest path in edges.

Common Mistakes#

1. Skipping the negative-cycle pass. Without the V-th iteration, you can return wrong distances. Always run one more pass for correctness.
2. Comparing against INF + weight overflow. Always guard with dist[u] != INF before computing dist[u] + w. Otherwise overflow can let an unreachable vertex falsely improve another's distance.
3. Using Bellman-Ford on non-negative-weight graphs in production. Dijkstra is O((V + E) log V), much faster. Use Bellman-Ford only when negatives are present or when constrained by hop count.
4. Confusing parent edges in negative cycles. When a negative cycle exists, parent[] chains may form a loop. Reconstruction algorithms must detect this.
5. Misreading "K stops" problems. LeetCode 787 caps the number of stops; that maps to running K + 1 Bellman-Ford rounds with one trick: relax against a snapshot of the previous round's distances to prevent multi-hop cascades within a single round.
6. Treating the source as 0 by default. Always initialize from the actual source and validate 0 &lt;= src < n.

Interview Tips#

• Open with: "Bellman-Ford runs in O(V * E) and works with negative edges. Its V-1-round structure is what makes the K-stop variant trivial."
• For LeetCode 787, walk through the snapshot trick: keep prev and curr arrays so a single round only adds at most one edge of distance per path.
• Mention SPFA (Shortest Path Faster Algorithm) as a queue-based optimisation that often runs much faster in practice but has the same worst case.
• For negative cycle detection, demonstrate that the V-th relaxation succeeding implies a cycle and explain the proof in one sentence: "after V-1 rounds, any shortest path has been found; a further improvement requires a cycle whose total weight is negative."
• Mention currency arbitrage as a real-world application — interviewers love when you connect algorithms to systems.

Follow-up Questions#

1. How to recover the negative cycle itself? Run the V-th relaxation, mark vertices that improved, then walk back parent[] for V steps to land inside the cycle.
2. What is SPFA? A queue-based variant that only relaxes edges out of vertices whose distance improved last round. Same O(V * E) worst case, faster in practice.
3. LeetCode 787 (Cheapest Flights Within K Stops): Run Bellman-Ford for K + 1 rounds using a copy of distances each round.
4. Currency arbitrage detection: Build edges with weight -log(rate). A negative cycle means a profitable trading loop.
5. Why does Dijkstra fail with negatives? Dijkstra commits a vertex's final distance the moment it pops it from the priority queue; a later negative edge could improve the distance, but the vertex is already finalised.

Key Takeaways#

• Bellman-Ford finds single-source shortest paths in O(V * E) and handles negative edges, unlike Dijkstra.
• After V - 1 rounds of relaxing every edge, distances are correct (assuming no negative cycle).
• A V-th relaxation pass detects negative cycles: any further improvement signals a cycle.
• Always guard relaxation with dist[u] != INF to avoid overflow on unreachable vertices.
• Early termination (no updates in a round) speeds it up significantly in practice.
• LeetCode 787 (K-stops cheapest flights) is the canonical FAANG interview application of Bellman-Ford's bounded-rounds property.