DSA Advanced

Bellman-Ford Algorithm Explained — Negative Weights, Cycle Detection & Production Pitfalls

📅 March 2026 ⏱ 8 min read 🎯 Advanced

In Plain English 🔥

Imagine you're planning a road trip and some roads give you fuel credits (negative cost) instead of costing you money. Dijkstra's algorithm would panic — it assumes every road costs you something. Bellman-Ford, on the other hand, is the calm navigator who says 'let me check every single road, multiple times, just to be sure I've found the cheapest route — even if some roads pay YOU to drive them.' It also warns you if there's a loop of fuel-credit roads that would let you drive forever for free, which would make any shortest-path answer meaningless.

⚡ Quick Answer

Financial trading systems use graph algorithms to find arbitrage opportunities — sequences of currency exchanges that yield profit. GPS routing engines handle toll roads, ferry routes, and restricted zones. Network packet routing protocols like RIP (Routing Information Protocol) propagate cost updates across distributed nodes. In every one of these systems, the edge weights on a graph can be negative. That single reality invalidates Dijkstra's algorithm entirely, and it's the reason Bellman-Ford exists.

The core problem Bellman-Ford solves is single-source shortest paths in a weighted directed graph where edge weights can be negative. Dijkstra's greedy approach assumes that once a node is 'settled' its shortest distance is final — a guarantee that collapses the moment a future negative edge could have produced a cheaper path. Bellman-Ford abandons the greedy assumption and instead performs exhaustive relaxation: it checks every edge, repeatedly, until it's mathematically certain no cheaper path exists. As a bonus, it can detect negative-weight cycles — loops in the graph where traversing the cycle keeps reducing your total cost to negative infinity, making shortest paths undefined.

By the end of this article you'll understand exactly why Bellman-Ford performs V-1 relaxation passes and not V or V-2, how to implement it correctly in Java with proper negative-cycle detection, where it outperforms Dijkstra in practice, what the subtle off-by-one bugs look like in interview code, and how production systems like distributed routing protocols derive their design directly from this algorithm's properties.

How Bellman-Ford Actually Works — The Relaxation Engine

The algorithm is built on one elegant insight: in a graph with V vertices, any shortest path that doesn't loop through a negative cycle can visit at most V-1 edges. Why? Because a simple path visits each vertex at most once, and connecting V vertices requires at most V-1 edges. That bound gives us our loop count.

The core operation is called relaxation. For every directed edge (u → v) with weight w, we ask: 'Is the known distance to v currently greater than the known distance to u plus w?' If yes, we've found a cheaper route to v, so we update it. We repeat this for every edge in the graph, V-1 times.

After V-1 passes, all shortest paths are guaranteed to be finalized — IF no negative cycles exist. The V-th pass is the negative-cycle detector. If any distance still relaxes on the V-th iteration, there's a vertex caught in a negative cycle: a cycle whose total weight is less than zero. Walking that cycle repeatedly reduces cost without bound, so shortest paths to reachable vertices become undefined (negative infinity).

This is fundamentally different from Dijkstra's priority-queue approach. There's no 'settled' set, no greedy extraction. Every edge is revisited every pass. That's what makes it O(V × E) — slower, but correct for the full problem space.

BellmanFordCore.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120

import java.util.Arrays;

public class BellmanFordCore {

    // Represents a directed, weighted edge in the graph
    static class Edge {
        int source;
        int destination;
        int weight;

        Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    /**
     * Runs Bellman-Ford from a given source vertex.
     *
     * @param edges     all edges in the graph
     * @param numVertices total number of vertices (labeled 0 to numVertices-1)
     * @param source    the starting vertex
     */
    static void bellmanFord(Edge[] edges, int numVertices, int source) {
        // Step 1: Initialize distances. Source is 0, everything else is infinity.
        // We use Long to avoid integer overflow when adding large weights.
        long[] distanceTo = new long[numVertices];
        Arrays.fill(distanceTo, Long.MAX_VALUE);
        distanceTo[source] = 0;

        // Step 2: Relax ALL edges exactly (numVertices - 1) times.
        // After pass k, distanceTo[v] holds the shortest path using AT MOST k edges.
        // After pass (V-1), all shortest simple paths are captured.
        for (int pass = 1; pass <= numVertices - 1; pass++) {
            boolean anyRelaxation = false; // early-exit optimisation

            for (Edge edge : edges) {
                // Only try to relax if the source vertex has been reached
                if (distanceTo[edge.source] == Long.MAX_VALUE) {
                    continue; // can't improve through an unreachable node
                }

                long newDistance = distanceTo[edge.source] + edge.weight;

                if (newDistance < distanceTo[edge.destination]) {
                    distanceTo[edge.destination] = newDistance;
                    anyRelaxation = true;
                    System.out.printf("  Pass %d: Relaxed edge %d→%d (weight %d). New dist[%d] = %d%n",
                            pass, edge.source, edge.destination, edge.weight,
                            edge.destination, newDistance);
                }
            }

            // If no edge was relaxed this pass, shortest paths are already final.
            // This is an optional O(V*E) → O(k*E) optimisation for sparse relaxation.
            if (!anyRelaxation) {
                System.out.printf("  Early exit after pass %d — no relaxation occurred.%n", pass);
                break;
            }
        }

        // Step 3: Negative-cycle detection — run ONE more pass.
        // If ANY edge can still be relaxed, that vertex is on or reachable from a negative cycle.
        System.out.println("\n--- Negative Cycle Detection (Pass V) ---");
        boolean negativeCycleFound = false;
        for (Edge edge : edges) {
            if (distanceTo[edge.source] == Long.MAX_VALUE) continue;

            if (distanceTo[edge.source] + edge.weight < distanceTo[edge.destination]) {
                System.out.printf("  Negative cycle detected! Edge %d→%d (weight %d) still relaxes.%n",
                        edge.source, edge.destination, edge.weight);
                negativeCycleFound = true;
            }
        }

        if (!negativeCycleFound) {
            System.out.println("  No negative cycle found. Results are valid.");
        }

        // Step 4: Print final shortest distances
        System.out.println("\n--- Shortest Distances from Vertex " + source + " ---");
        for (int vertex = 0; vertex < numVertices; vertex++) {
            String distDisplay = (distanceTo[vertex] == Long.MAX_VALUE)
                    ? "UNREACHABLE"
                    : String.valueOf(distanceTo[vertex]);
            System.out.printf("  dist[%d] = %s%n", vertex, distDisplay);
        }
    }

    public static void main(String[] args) {
        // Graph with 5 vertices (0-4) and a negative edge (not a negative cycle)
        // Topology:
        //  0 --(6)--> 1
        //  0 --(7)--> 2
        //  1 --(5)--> 2
        //  1 --(8)--> 3
        //  1 --(-4)--> 4
        //  2 --(-3)--> 3
        //  3 --(9)--> 1   <-- forms a cycle, but total weight is positive: 8+(-3)+9 = 14
        //  4 --(7)--> 3
        //  4 --(2)--> 0

        int numVertices = 5;
        Edge[] edges = {
                new Edge(0, 1, 6),
                new Edge(0, 2, 7),
                new Edge(1, 2, 5),
                new Edge(1, 3, 8),
                new Edge(1, 4, -4),
                new Edge(2, 3, -3),
                new Edge(3, 1, 9),
                new Edge(4, 3, 7),
                new Edge(4, 0, 2)
        };

        System.out.println("=== Bellman-Ford from Source Vertex 0 ===\n");
        bellmanFord(edges, numVertices, 0);
    }
}

▶ Output

=== Bellman-Ford from Source Vertex 0 ===

Pass 1: Relaxed edge 0→1 (weight 6). New dist[1] = 6
Pass 1: Relaxed edge 0→2 (weight 7). New dist[2] = 7
Pass 1: Relaxed edge 1→2 (weight 5). New dist[2] = 11
Pass 1: Relaxed edge 1→3 (weight 8). New dist[3] = 14
Pass 1: Relaxed edge 1→4 (weight -4). New dist[4] = 2
Pass 1: Relaxed edge 2→3 (weight -3). New dist[3] = 8
Pass 1: Relaxed edge 4→3 (weight 7). New dist[3] = 9
Pass 2: Relaxed edge 2→3 (weight -3). New dist[3] = 4
Pass 2: Relaxed edge 3→1 (weight 9). New dist[1] = 13
Pass 3: Relaxed edge 1→4 (weight -4). New dist[4] = 9
Pass 4: Early exit after pass 4 — no relaxation occurred.

--- Negative Cycle Detection (Pass V) ---
No negative cycle found. Results are valid.

--- Shortest Distances from Vertex 0 ---
dist[0] = 0
dist[1] = 13
dist[2] = 7
dist[3] = 4
dist[4] = 9

🔥

Why V-1 Passes and Not V?A shortest path in a graph with V vertices has at most V-1 edges — any more and it must revisit a vertex, forming a cycle. After V-1 relaxation passes, every possible simple path has been explored. The V-th pass is reserved exclusively for negative-cycle detection. Use exactly this split: V-1 for finding paths, 1 for detecting cycles.

Negative Cycle Detection — Finding and Propagating Infinity

Detecting that a negative cycle exists is only half the job. In production systems — like currency arbitrage detectors or network routing daemons — you often need to know WHICH vertices are affected by a negative cycle, not just that one exists.

A vertex affected by a negative cycle isn't necessarily part of the cycle itself. It can simply be reachable FROM a cycle. Any vertex reachable from a negative cycle also has an undefined (negative infinity) shortest path, because you could loop the cycle as many times as you like before reaching it.

The standard fix is a two-phase approach after the V-1 relaxation passes. Phase one: run the V-th pass and mark every vertex that still relaxes as 'cycle-affected.' Phase two: run a BFS or DFS from every marked vertex to propagate the 'negative infinity' flag to all vertices reachable from them.

This is the version production systems actually need. A routing protocol that just reports 'negative cycle somewhere' without isolating the contaminated vertices is useless — you need to know which routes are still trustworthy.

The implementation below extends the core algorithm to propagate negative-infinity contamination correctly, which is what you'd actually ship in a financial or network system.

NegativeCycleDetector.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102

import java.util.*;

public class NegativeCycleDetector {

    static class Edge {
        int source, destination, weight;
        Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    static final long NEG_INFINITY = Long.MIN_VALUE; // sentinel for "tainted by negative cycle"

    static long[] bellmanFordWithCyclePropagation(Edge[] edges, int numVertices, int source) {
        long[] distanceTo = new long[numVertices];
        Arrays.fill(distanceTo, Long.MAX_VALUE);
        distanceTo[source] = 0;

        // Standard V-1 relaxation passes
        for (int pass = 0; pass < numVertices - 1; pass++) {
            for (Edge edge : edges) {
                if (distanceTo[edge.source] == Long.MAX_VALUE) continue;
                long candidate = distanceTo[edge.source] + edge.weight;
                if (candidate < distanceTo[edge.destination]) {
                    distanceTo[edge.destination] = candidate;
                }
            }
        }

        // Phase 1: Identify vertices that are DIRECTLY on or adjacent to a negative cycle.
        // These are vertices whose distance still decreases on the V-th pass.
        Set<Integer> cycleAffectedSeeds = new HashSet<>();
        for (Edge edge : edges) {
            if (distanceTo[edge.source] == Long.MAX_VALUE) continue;
            if (distanceTo[edge.source] + edge.weight < distanceTo[edge.destination]) {
                // Both source and destination are cycle-affected seeds
                cycleAffectedSeeds.add(edge.source);
                cycleAffectedSeeds.add(edge.destination);
            }
        }

        // Phase 2: BFS to propagate NEG_INFINITY to ALL vertices reachable from cycle seeds.
        // Build an adjacency list for efficient BFS traversal.
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
        for (int vertex = 0; vertex < numVertices; vertex++) {
            adjacencyList.put(vertex, new ArrayList<>());
        }
        for (Edge edge : edges) {
            adjacencyList.get(edge.source).add(edge.destination);
        }

        Queue<Integer> bfsQueue = new LinkedList<>(cycleAffectedSeeds);
        Set<Integer> visited = new HashSet<>(cycleAffectedSeeds);

        while (!bfsQueue.isEmpty()) {
            int currentVertex = bfsQueue.poll();
            distanceTo[currentVertex] = NEG_INFINITY; // taint this vertex

            for (int neighbour : adjacencyList.get(currentVertex)) {
                if (!visited.contains(neighbour)) {
                    visited.add(neighbour);
                    bfsQueue.add(neighbour); // propagate taint forward
                }
            }
        }

        return distanceTo;
    }

    public static void main(String[] args) {
        // Graph designed to have a genuine negative cycle: 1 → 2 → 3 → 1
        // Cycle weight: (-1) + (-2) + (-3) = -6 (negative — loops forever)
        // Vertex 4 is REACHABLE from vertex 3, so it's also tainted.
        // Vertex 0 is the source; vertex 5 is unreachable entirely.
        int numVertices = 6;
        Edge[] edges = {
                new Edge(0, 1, 5),    // source reaches vertex 1
                new Edge(1, 2, -1),   // part of negative cycle
                new Edge(2, 3, -2),   // part of negative cycle
                new Edge(3, 1, -3),   // completes negative cycle (total: -6)
                new Edge(3, 4, 10),   // vertex 4 reachable FROM the cycle — tainted!
                // vertex 5 has no incoming edges — unreachable
        };

        System.out.println("=== Negative Cycle Propagation Demo ===\n");
        long[] distances = bellmanFordWithCyclePropagation(edges, numVertices, 0);

        for (int vertex = 0; vertex < numVertices; vertex++) {
            String result;
            if (distances[vertex] == Long.MAX_VALUE) {
                result = "UNREACHABLE";
            } else if (distances[vertex] == NEG_INFINITY) {
                result = "−∞  (tainted by negative cycle)";
            } else {
                result = String.valueOf(distances[vertex]);
            }
            System.out.printf("  dist[%d] = %s%n", vertex, result);
        }
    }
}

▶ Output

=== Negative Cycle Propagation Demo ===

dist[0] = 0
dist[1] = −∞ (tainted by negative cycle)
dist[2] = −∞ (tainted by negative cycle)
dist[3] = −∞ (tainted by negative cycle)
dist[4] = −∞ (tainted by negative cycle)
dist[5] = UNREACHABLE

⚠️

Watch Out: 'Unreachable' ≠ 'Tainted'Two completely different failure modes look similar if you use a single sentinel value like -1. Use THREE distinct states: a large positive sentinel for 'unreachable,' a large negative sentinel for 'tainted by negative cycle,' and actual computed values for valid distances. Conflating the first two is a silent correctness bug — your code runs, returns garbage, and tells you nothing.

Bellman-Ford vs Dijkstra — Choosing the Right Tool

The question isn't which algorithm is better — it's which algorithm is correct for your graph. Dijkstra is faster but makes an assumption that breaks on negative weights. Bellman-Ford is slower but makes no such assumption.

Dijkstra's complexity is O((V + E) log V) with a binary heap, versus Bellman-Ford's O(V × E). For a dense graph with V=1000 and E=500,000, Dijkstra runs around 10 million operations while Bellman-Ford runs 500 million. That's a 50× difference — significant in hot code paths.

But here's the nuance that trips up senior engineers: Dijkstra with a simple re-weighting trick (Johnson's Algorithm) can handle negative edges on dense graphs by running Bellman-Ford ONCE from a dummy source to compute re-weighting offsets, then running Dijkstra from every real source. This is how all-pairs shortest paths with negative edges achieves O(V² log V + VE) instead of O(V² × E) for Bellman-Ford on every source.

For distributed systems, Bellman-Ford has another advantage: it's inherently parallelisable per-edge and works asynchronously. RIP and BGP distance-vector routing are direct descendants. Each router runs a local version, sharing distance vectors with neighbours — a distributed Bellman-Ford at network scale.

Choose Bellman-Ford when: edge weights can be negative, negative-cycle detection is required, the graph is sparse (E ≈ V), or you're building a distributed system where asynchronous relaxation is natural.

ShortestPathComparison.java · JAVA

import java.util.*;

/**
 * Side-by-side demonstration of Bellman-Ford vs Dijkstra on the same graph.
 * Dijkstra deliberately fails on the negative-weight graph to illustrate
 * why algorithm selection matters — not just performance, but correctness.
 */
public class ShortestPathComparison {

    static class Edge {
        int source, destination, weight;
        Edge(int s, int d, int w) { source = s; destination = d; weight = w; }
    }

    // ---- Bellman-Ford (handles negative weights correctly) ----
    static long[] bellmanFord(List<Edge> edges, int numVertices, int source) {
        long[] dist = new long[numVertices];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[source] = 0;

        for (int pass = 0; pass < numVertices - 1; pass++) {
            for (Edge edge : edges) {
                if (dist[edge.source] != Long.MAX_VALUE
                        && dist[edge.source] + edge.weight < dist[edge.destination]) {
                    dist[edge.destination] = dist[edge.source] + edge.weight;
                }
            }
        }
        return dist;
    }

    // ---- Dijkstra (WRONG on negative weights — shown for contrast) ----
    static long[] dijkstra(List<Edge>[] adjacency, int numVertices, int source) {
        long[] dist = new long[numVertices];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[source] = 0;

        // PriorityQueue ordered by distance: [distance, vertex]
        PriorityQueue<long[]> minHeap = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        minHeap.offer(new long[]{0, source});

        boolean[] settled = new boolean[numVertices];

        while (!minHeap.isEmpty()) {
            long[] current = minHeap.poll();
            long currentDist = current[0];
            int currentVertex = (int) current[1];

            if (settled[currentVertex]) continue;
            settled[currentVertex] = true; // greedy assumption: this is final — WRONG if negative edges exist

            for (Edge edge : adjacency[currentVertex]) {
                if (!settled[edge.destination] && currentDist + edge.weight < dist[edge.destination]) {
                    dist[edge.destination] = currentDist + edge.weight;
                    minHeap.offer(new long[]{dist[edge.destination], edge.destination});
                }
            }
        }
        return dist;
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        // Graph: 4 vertices, negative edge on path 0→2→3
        //  0 --(1)--> 1
        //  0 --(4)--> 2
        //  1 --(3)--> 2
        //  2 --(-5)--> 3  <-- negative edge! Dijkstra settles vertex 2 too early.
        //  1 --(2)--> 3
        //
        // Correct shortest path 0→3: 0→2→3 = 4 + (-5) = -1
        // Dijkstra picks:           0→1→3 = 1 + 2    =  3  (WRONG)

        int numVertices = 4;

        List<Edge> edgeList = Arrays.asList(
                new Edge(0, 1, 1),
                new Edge(0, 2, 4),
                new Edge(1, 2, 3),
                new Edge(2, 3, -5),  // the negative edge Dijkstra cannot handle
                new Edge(1, 3, 2)
        );

        // Build adjacency list for Dijkstra
        List<Edge>[] adjacency = new List[numVertices];
        for (int i = 0; i < numVertices; i++) adjacency[i] = new ArrayList<>();
        for (Edge edge : edgeList) adjacency[edge.source].add(edge);

        long[] bfResult = bellmanFord(edgeList, numVertices, 0);
        long[] dijkResult = dijkstra(adjacency, numVertices, 0);

        System.out.println("=== Algorithm Comparison (Source: Vertex 0) ===");
        System.out.printf("%-10s %-20s %-20s%n", "Vertex", "Bellman-Ford", "Dijkstra (buggy)");
        System.out.println("-".repeat(52));
        String[] correctness = {"", "", "", "← Dijkstra WRONG here!"};
        for (int v = 0; v < numVertices; v++) {
            System.out.printf("%-10d %-20s %-20s %s%n", v,
                    bfResult[v] == Long.MAX_VALUE ? "UNREACHABLE" : bfResult[v],
                    dijkResult[v] == Long.MAX_VALUE ? "UNREACHABLE" : dijkResult[v],
                    correctness[v]);
        }
        System.out.println("\nNote: dist[3] correct answer is -1. Dijkstra returns 3.");
    }
}

▶ Output

=== Algorithm Comparison (Source: Vertex 0) ===
Vertex Bellman-Ford Dijkstra (buggy)
----------------------------------------------------
0 0 0
1 1 1
2 4 4
3 -1 3 ← Dijkstra WRONG here!

Note: dist[3] correct answer is -1. Dijkstra returns 3.

⚠️

Pro Tip: The Early-Exit OptimisationTrack whether any edge was relaxed during a full pass. If a complete pass over all edges produces zero relaxations, shortest paths are already final — you can break early. In practice on sparse graphs with few negative edges, this often cuts the actual number of passes to far fewer than V-1. The worst-case complexity stays O(V×E), but the average case improves meaningfully.

Feature / Aspect	Bellman-Ford	Dijkstra
Time Complexity	O(V × E)	O((V + E) log V) with binary heap
Space Complexity	O(V) for distances + O(E) for edge list	O(V) for distances + O(V) for priority queue
Negative Edge Weights	✅ Fully supported	❌ Produces incorrect results
Negative Cycle Detection	✅ Built-in with V-th pass	❌ Not supported — undefined behaviour
Graph Type	Directed (adaptable to undirected)	Directed and undirected
Implementation Complexity	Simple — flat edge-list loop	Moderate — requires priority queue
Distributed Systems Use	✅ Foundation of RIP, distance-vector routing	❌ Requires global state — not distributed-friendly
Dense Graph Performance	Poor — O(V³) on complete graph	Good — O(V² log V) on complete graph
Sparse Graph Performance	Good when E ≈ V	Excellent when E ≈ V
All-Pairs Shortest Paths	O(V² × E) — very slow	Better via Johnson's Algorithm (run BF once, Dijkstra V times)

🎯 Key Takeaways

⚠ Common Mistakes to Avoid

✕Mistake 1: Running exactly V passes instead of V-1 for relaxation, then having no V-th pass for detection — The algorithm appears to work on graphs without negative cycles, but silently skips negative-cycle detection entirely. Any graph with a negative cycle returns plausible-looking but meaningless distances. Fix: use a loop for (pass = 0; pass < numVertices - 1; pass++) for relaxation, then a separate loop after it for detection — never conflate the two.
✕Mistake 2: Using Integer.MAX_VALUE as the initial distance sentinel and adding a positive weight to it — This causes integer overflow, wrapping around to a large negative number. Suddenly every edge looks like it relaxes, and the output is garbage with no error thrown. Fix: use Long.MAX_VALUE with a long[] distance array, or add an explicit guard if (distanceTo[source] != Long.MAX_VALUE) before attempting relaxation.
✕Mistake 3: Declaring 'no negative cycle' simply because no relaxation fires on the V-th pass from your specific source — If the negative cycle is in a disconnected component or unreachable from your source, Bellman-Ford won't see it. The correct fix for full-graph negative-cycle detection is to add a dummy super-source vertex with zero-weight edges to every other vertex, run Bellman-Ford from that super-source, and perform the V-th pass check. This is exactly what Johnson's Algorithm does as its preprocessing step.

Interview Questions on This Topic

QWhy does Bellman-Ford require exactly V-1 relaxation passes? What is the mathematical invariant that holds after pass k, and why does that invariant guarantee correctness after pass V-1?
QHow would you modify Bellman-Ford to not only detect a negative cycle but also return the actual vertices forming that cycle? Walk me through the implementation — what data structure tracks the predecessor path, and how do you extract the cycle from it?
QDijkstra can be made to work with negative edges if you add a large constant to every edge weight to make them all non-negative. Why doesn't this work? Construct a specific counterexample with three vertices that demonstrates the flaw.

🔥

TheCodeForge Editorial Team Verified Author

Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.

About Our Team Editorial Standards

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged