Bellman-Ford Visualization for Coding Interviews

V-1 relax rounds; handles negative edges, detects negative cycles.

Concept

Bellman-Ford is the shortest-path algorithm that accepts what Dijkstra rejects: negative edge weights. Its guarantees are weaker only in the sense of runtime - it still produces correct single-source shortest paths in O(V*E), and uniquely among the common algorithms it can detect the presence of a negative-weight cycle reachable from the source. That detection property is why Bellman-Ford shows up far beyond textbook routing: currency-arbitrage detection, constraint systems like difference constraints, and distance-vector routing protocols such as RIP. Algorithmically it is almost trivial - relax every edge V-1 times and you are done - yet the proof of correctness is subtle and depends on an inductive claim about the shortest path length. For graphs where most edges are irrelevant you can add an early-exit: stop as soon as a full pass performs no relaxations. For graphs where you want the parent tree, keep a parent[] array and reconstruct paths exactly as you would with Dijkstra.

How it works

Initialize dist[src] = 0 and every other distance to a large sentinel. Then perform V-1 passes over the entire edge list. In each pass, for every edge (u, v, w), if dist[u] + w < dist[v], update dist[v] = dist[u] + w and set parent[v] = u. The inductive invariant is that after k passes, dist[v] holds the cost of the shortest path from src to v that uses at most k edges. Because any acyclic shortest path has at most V-1 edges, V-1 passes suffice when no negative cycle exists. The negative-cycle check is the elegant part: run a V-th pass. If any edge can still be relaxed on that pass, a negative-weight cycle is reachable from the source - because otherwise the invariant should already hold. You can even mark which vertices are "poisoned" by the cycle by running BFS/DFS from any successfully-relaxed vertex. Practical optimization: break out of the relaxation loop early the first pass that performs zero relaxations, since no further updates can ever occur. SPFA is a queue-based variant that is faster in practice but has the same worst-case bound.

Implementation

import java.util.*;

public class BellmanFord {
    public static final long INF = Long.MAX_VALUE / 4;  // headroom to avoid overflow on relax

    public static class Result {
        public final long[] dist;
        public final int[] parent;
        public final boolean hasNegativeCycle;

        public Result(long[] dist, int[] parent, boolean hasNegativeCycle) {
            this.dist = dist; this.parent = parent; this.hasNegativeCycle = hasNegativeCycle;
        }
    }

    /**
     * edges[i] = {u, v, w} directed edge u -> v of weight w (w may be negative).
     * Returns dist[], parent[], and whether a negative cycle is reachable from src.
     */
    public static Result bellmanFord(int[][] edges, int n, int src) {
        long[] dist = new long[n];
        int[] parent = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);
        dist[src] = 0L;

        // V-1 relaxation passes; stop early if a pass does nothing.
        for (int pass = 0; pass < n - 1; pass++) {
            boolean anyRelaxed = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] == INF) continue;
                long nd = dist[u] + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    parent[v] = u;
                    anyRelaxed = true;
                }
            }
            if (!anyRelaxed) break;
        }

        // V-th pass: any further relaxation implies a negative cycle is reachable.
        boolean hasNegCycle = false;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] == INF) continue;
            if (dist[u] + w < dist[v]) { hasNegCycle = true; break; }
        }
        return new Result(dist, parent, hasNegCycle);
    }
}

Complexity

• Time: O(V * E)
• Space: O(V)

Common pitfalls

• Relaxing dist[u] + w without first checking dist[u] != INF, which causes silent overflow when INF is Long.MAX_VALUE.
• Running only V-2 passes off a fencepost error and missing a legitimate update on the last layer.
• Reporting a negative cycle that is not reachable from the source - the V-th pass only flags cycles the source can actually reach.
• Using Bellman-Ford on a huge graph when Dijkstra would work; V*E gets painful past a few thousand vertices.
• Failing to set parent[src] = -1 and producing a bogus path when reconstructing back to the source.

Key design decisions & trade-offs

• Relaxation ordering — Chosen: Fixed edge-list order with V-1 passes. Simple, predictable, and correct regardless of edge order; SPFA can be faster in practice but has the same worst case.
• INF sentinel — Chosen: Long.MAX_VALUE / 4. Leaves headroom for dist[u] + w without overflowing; using MAX_VALUE directly wraps and corrupts comparisons.
• Cycle detection granularity — Chosen: Boolean flag on V-th pass. Matches the typical interview/LeetCode ask; for deeper analysis, mark every relaxed vertex as poisoned and propagate.

Practice problems

• Cheapest Flights Within K Stops

Interview follow-ups

• SPFA (queue-based relaxation) for practical speedup on sparse graphs.
• Johnson's algorithm for all-pairs shortest paths with negative edges.
• Difference-constraint systems solved as shortest paths in a constraint graph.
• Detect and return the cycle itself, not just a boolean, by walking parents from a relaxed vertex.
• Apply Bellman-Ford to currency-arbitrage detection on a log-transformed exchange graph.

Why it matters

Bellman-Ford is a core part of the Graphs toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related

• Dijkstra
• Floyd-Warshall
• Topological Sort