A checkout router picks the cheapest path through payment hops. Edges are fees in cents. One hop is a partner rebate: −400. The first version copied the mesh Dijkstra: settle the closest vertex, never reopen. It settled B at 200 via the direct fee. A path through the rebate would have made B cost 100. The invoice used 200. Nobody “chose a slow algorithm.” They ran a non-negative procedure past a negative edge.

Bellman-Ford keeps relaxing after a vertex would have been “settled” — a cheaper path through a negative edge can appear later. After V-1 passes every honest shortest path (no negative cycle) has been found; one more pass that still improves means a negative cycle is reachable from the source. The layout is a weighted adjacency list (Graphs). Families and the catalog live on the Algorithms Roadmap. Non-negative single-source is Dijkstra. It is not Dijkstra with a flag, not a geo-SDK tutorial, and not a reason to scan every edge V times on a graph whose every weight is ≥ 0.

The non-negative case already lives on the Dijkstra page. This post does not re-teach the heap, stale pops, or lazy re-push. Those stay there.

A negative edge can cheapen a vertex after Dijkstra would have settled it. Reopening settled vertices “just in case” is not Dijkstra with a flag — it is a different procedure: look at every edge, many times. Zero is still a legal weight. A mix of negative, zero, and positive is why you are here. A negative cycle reachable from the source is why the extra pass exists: there is then no finite shortest path.

SPFA is a name for a queue-ordered variant of the same relaxations. This post does not implement it.

Dijkstra plus a negative-weight flag is not a shortest-path strategy. Neither is Bellman-Ford on a unit graph you could have queued.

Relax every edge, V-1 times

Start at a source s. Distances begin at infinity except dist[s] = 0. Repeatedly:

  1. Pass. For every edge u → v of weight w, if dist[u] is finite and dist[u] + w < dist[v], write the new distance.
  2. Repeat that pass V-1 times. A simple path has at most V-1 edges; each pass can extend the cheapest known path by one edge.
  3. Detect. Run the same pass once more. If any distance still improves, a negative cycle is reachable from s.

You do not grow a settled set. You do not pop a heap. Order of edges inside a pass can change when a better path shows up, not whether it shows up by pass V-1.

Note: Directed or undirected is the layout’s job. An undirected negative edge is immediately a two-cycle of negative weight. Bellman-Ford will (correctly) flag it. If the domain is a credit on a one-way hop, the edge is directed.

A walked pass Dijkstra would settle too early

Four vertices. Direct A → B looks cheapest first. The rebate C → B is negative and arrives from a vertex Dijkstra would expand later.

directed, one negative edge:

  A --2--> B --1--> D
  |        ^
  5        -4
  v        |
  C -------+

dist: A=0, B=C=D=∞
edges in this order: B→D, C→B, A→B, A→C

If you settled B at 2 and never reopened: D becomes 3 and stays 3. Dijkstra’s first-pop-is-final rule is why. The real cheapest path is A → C → B → D at cost 2. Bellman-Ford does not settle; it keeps scanning.

pass 1
  B→D  dist[B]=∞   skip
  C→B  dist[C]=∞   skip
  A→B  dist[B]=2
  A→C  dist[C]=5
dist: A=0, B=2, C=5, D=∞

pass 2
  B→D  dist[D]=3
  C→B  dist[B]=1     (5 + -4)
  A→B  2 vs 1        no
  A→C  no
dist: A=0, B=1, C=5, D=3

pass 3   (V-1 = 3)
  B→D  dist[D]=2     (1 + 1)
  C→B  1 vs 1        no
  A→B  no
  A→C  no
dist: A=0, B=1, C=5, D=2

detection pass: no distance improves
path A→D:  A → C → B → D   cost 2
not:       A → B → D       cost 3

The cheaper path through C showed up after B already had a finite distance. That is the whole argument against settling. Empty graph and a source with no edges: dist[s] = 0, every pass is a no-op, everyone else stays unreachable.

Java sketch

Weighted list as in the graph post: Edge(to, weight). Flatten to “every edge” by walking each vertex’s outgoing list. The extra loop is the cycle detector, not a second algorithm.

record Edge(String to, int weight) {}
record Result(Map<String, Integer> dist, boolean negativeCycle) {}

static Result bellmanFord(Map<String, List<Edge>> g, String src) {
    Map<String, Integer> dist = new HashMap<>();
    for (String v : g.keySet()) {
        dist.put(v, Integer.MAX_VALUE);
    }
    dist.put(src, 0);

    int V = g.size();
    for (int pass = 0; pass < V - 1; pass++) {
        for (String u : g.keySet()) {
            int du = dist.get(u);
            if (du == Integer.MAX_VALUE) {
                continue; // unreachable; do not relax from sentinel
            }
            for (Edge e : g.getOrDefault(u, List.of())) {
                long nd = (long) du + e.weight();
                int best = dist.getOrDefault(e.to(), Integer.MAX_VALUE);
                if (nd < best) {
                    dist.put(e.to(), (int) nd);
                }
            }
        }
    }

    boolean neg = false;
    for (String u : g.keySet()) {
        int du = dist.get(u);
        if (du == Integer.MAX_VALUE) {
            continue;
        }
        for (Edge e : g.getOrDefault(u, List.of())) {
            long nd = (long) du + e.weight();
            if (nd < dist.getOrDefault(e.to(), Integer.MAX_VALUE)) {
                neg = true;
            }
        }
    }
    return new Result(dist, neg);
}

Keep a prev map beside dist if you must emit the path: when you write a better dist[v], set prev[v] = u, then walk backward from the destination. Do not store path prefixes on the edge list.

Vertices that appear only as Edge.to need a putIfAbsent when you add edges, same as the graph post’s addVertex. The sketch assumes the map already has every vertex key.

Note: Integer.MAX_VALUE + weight wraps to a negative int. The long add is the guard. Unreachable vertices left at MAX_VALUE are a sentinel, not a cost you may add to. Skip those u before relaxing.

Complexity

Let V be vertices, E edges. Each of V-1 passes scans every edge; the detection pass does the same.

TimeO(VE)
Extra RAMDistances, optional prev — not a path matrix
After V-1 passesShortest s ⇝ v if no negative cycle on that path
Extra pass still improvesNegative cycle reachable from s

Glossary and the Big-O reading live on the hub. The bill that kills the checkout router is settling too early, not a missing queue optimization.

If you only need s to one t, you still run the V-1 passes: a cheaper path to t can appear on the last honest pass. Worst case you still scan every edge every pass.

When not to run Bellman-Ford

Skip it when:

  • Every weight is ≥ 0. Dijkstra already returns shortest path. Scanning every edge V times is cargo-cult of the name.
  • Every edge is 1 / unweighted. BFS already answers. A V-1 sweep of unit edges is the same cargo-cult.
  • You needed “is u connected to v?” That is hasEdge / a reachability walk, not a distance.
  • A library already routes. Map SDKs, service-mesh control planes, and graph DBs already run a shortest-path procedure. Pasting this sketch into a request path is the wrong system boundary.

Do not bolt a negative-weight flag onto Dijkstra and reopen settled vertices. That is this algorithm, written badly.

Also skip it when there is no source: all-pairs on tiny n is a different procedure (Floyd-Warshall, Wave 4). This post is single-source.

JDK: no BellmanFord class

There is no java.util.BellmanFord. The library piece is the layout:

  • Layout: Map<K, List<Edge>> as in the graph post
  • Distances: a Map or array you initialize yourself
  • Optional path: a prev map you fill on relax
  • Cycle flag: the boolean from the extra pass

Prefer Dijkstra when every weight stays ≥ 0. Reach for the sketch when a weight is negative, or when you must prove no negative cycle is reachable from the source.

Do not wrap Dijkstra in a “if negative, reopen” branch. Do not sort the edge list on every pass. Do not invent a second queue-shaped procedure because a comment named one.

Cheat sheet

Job:        single-source shortest path; a weight may be negative
Loop:       relax every edge, V-1 times
Detect:     one more pass; still improving → negative cycle from s
Settle:     do not — a cheaper path can appear later
Dijkstra:   enough when every weight ≥ 0
BFS:        enough when every edge is 1 / unweighted
JDK:        no BellmanFord type; Map + Edge list; long add vs wrap
Do not:     Dijkstra-with-a-flag; O(VE) on non-negative graphs; a second queue variant

Do:

  • Scan every edge each pass. Order inside a pass does not replace V-1.
  • Skip unreachable u (dist[u] still sentinel) before adding w.
  • Treat the extra pass as the cycle detector, not as “one more for luck.”

Don’t:

  • Settle a vertex because its current distance looks smallest when a negative edge still sits unprocessed.
  • Add Integer.MAX_VALUE to a weight without a long guard.
  • Run this procedure on a unit graph, or on a non-negative graph Dijkstra already owns.
  • Treat an undirected negative edge as a normal two-way fee — it is a negative cycle.

Wrap-up

Bellman-Ford is single-source shortest path when a negative edge is legal. Relax every edge V-1 times, then one more pass: if a distance still improves, a negative cycle is reachable from the source. You may keep writing a cheaper dist[v] after Dijkstra would have settled v. The JDK gives you a map and an edge list, not a turnkey router. Use Dijkstra when every weight is ≥ 0. Use BFS when every edge is 1. Hand-roll the sketch when a rebate (or any negative weight) is in the graph, and you need the distances or the cycle flag.

The next procedure in this wave fills every pair, not one source: all-pairs when n is small enough for n³.

Next optional step in the series All-pairs when n is small enough for n³. Floyd-Warshall: All-Pairs When n Is Small Enough for n³