Negative Weight Cycle and the Bellman-Ford Algorithm for Single-Source Shortest Distance

A negative weight cycle in a directed graph is a cycle such that the sum of the weights of all edges on that cycle is negative.2 If such a cycle is reachable from the source vertex, then the shortest path problem becomes ill-defined, because traversing the cycle repeatedly keeps decreasing the total path cost without bound.2 In effect, the path cost can be pushed toward $-\infty$, so no finite shortest distance exists for vertices reachable through that cycle.2

The Bellman-Ford algorithm solves the single-source shortest-distance problem in weighted directed graphs even when some edge weights are negative, provided there is no reachable negative weight cycle.2 Its core idea is relaxation: for every edge $(u,v)$ with weight $w(u,v)$, if

$$d[u] + w(u,v) < d[v],$$

then the estimate $d[v]$ is improved.2

A key theoretical fact is that any simple path in a graph with $|V|$ vertices contains at most $|V|-1$ edges. Therefore, after relaxing all edges exactly $|V|-1$ times, Bellman-Ford computes correct shortest distances from the source to all reachable vertices if no reachable negative cycle exists.2

In the conceptual graph above, if the cycle $A \to B \to C \to A$ has total weight $< 0$, then every route from $S$ to $T$ through that cycle can be made cheaper by looping one more time before proceeding to $T$.2

Footnotes

1. Bellman–Ford Algorithm - GeeksforGeeks - Explains Bellman-Ford, relaxation, and negative cycle detection with the extra pass. ↩ ↩² ↩³

2. CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS - CLRS-based treatment of Bellman-Ford correctness, shortest paths, and reachable negative cycles. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

3. Bellman-Ford and Floyd-Warshall 1 Single Source Shortest Path - Notes explaining why negative cycles make shortest paths ill-defined and can drive distances to negative infinity. ↩

4. DP: Single Source Shortest Paths, The Bellman-Ford Algorithm - University notes discussing directed graphs, negative edges, and why negative cycles invalidate shortest-path computation. ↩

5. Bellman-Ford - finding shortest paths with negative weights - Provides algorithm intuition, complexity, and the criterion for negative-cycle detection. ↩ ↩²

Why negative weight cycles matter

In graphs with only positive weights, every additional cycle increases or preserves path cost. With negative cycles, repeated traversal keeps lowering the path total.2 This is why shortest-distance computation in such a graph is not just difficult; it is mathematically undefined for vertices reachable from the cycle.2

Suppose a cycle has total weight $-3$. If a path from source $s$ reaches that cycle, then after going around it $k$ times, the path cost decreases by $3k$. Since $k$ can be arbitrarily large,

$$\lim_{k \to \infty} \text{cost}(P) - 3k = -\infty.$$

Hence, no minimum finite distance exists.2

This distinction is important:

Important distance estimate, predecessor, and reachability concepts determine exactly which vertices are affected.2

Footnotes

1. CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS - CLRS-based treatment of Bellman-Ford correctness, shortest paths, and reachable negative cycles. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

2. Bellman-Ford and Floyd-Warshall 1 Single Source Shortest Path - Notes explaining why negative cycles make shortest paths ill-defined and can drive distances to negative infinity. ↩ ↩²

3. DP: Single Source Shortest Paths, The Bellman-Ford Algorithm - University notes discussing directed graphs, negative edges, and why negative cycles invalidate shortest-path computation. ↩

4. Bellman–Ford Algorithm - GeeksforGeeks - Explains Bellman-Ford, relaxation, and negative cycle detection with the extra pass. ↩

5. Bellman-Ford - finding shortest paths with negative weights - Provides algorithm intuition, complexity, and the criterion for negative-cycle detection. ↩ ↩²

Standard Bellman-Ford pseudocode

Let $G=(V,E)$ be a weighted directed graph and $s$ be the source.

1BELLMAN-FORD(G, w, s)
21. for each vertex v in V:
32.     d[v] = ∞
43.     π[v] = NIL
54. d[s] = 0
6
75. for i = 1 to |V| - 1:
86.     for each edge (u, v) in E:
97.         if d[u] ≠ ∞ and d[u] + w(u, v) < d[v]:
108.             d[v] = d[u] + w(u, v)
119.             π[v] = u
12
1310. for each edge (u, v) in E:
1411.     if d[u] ≠ ∞ and d[u] + w(u, v) < d[v]:
1512.         return "Negative weight cycle reachable from source"
16
1713. return d, π

This algorithm runs in

$$O(|V||E|)$$

time, because it scans all edges $|V|-1$ times plus one final pass, and uses

$$O(|V|)$$

extra space for distance and predecessor arrays.2

A useful correctness intuition is: after the $i$-th full pass, Bellman-Ford has correctly computed shortest distances for all vertices whose shortest path uses at most $i$ edges.2

Footnotes

1. CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS - CLRS-based treatment of Bellman-Ford correctness, shortest paths, and reachable negative cycles. ↩

2. Bellman-Ford - finding shortest paths with negative weights - Provides algorithm intuition, complexity, and the criterion for negative-cycle detection. ↩ ↩²

3. Shortest Paths II: Bellman-Ford - MIT 6.006 Lecture Notes - Formal lecture notes on Bellman-Ford correctness and path-length interpretation by iteration. ↩

Worked example

Consider the weighted directed graph with source $S$:

There is no negative cycle here, although one edge has negative weight.2

Initialization

• $d[S]=0$
• $d[A]=d[B]=d[C]=\infty$

Pass 1

• Relax $S \to A$: $d[A]=4$
• Relax $S \to B$: $d[B]=5$
• Relax $A \to B$: $d[B]=\min(5,4-2)=2$
• Relax $A \to C$: $d[C]=10$
• Relax $B \to C$: $d[C]=\min(10,2+3)=5$

After pass 1:

• $d[S]=0$, $d[A]=4$, $d[B]=2$, $d[C]=5$

Pass 2 No value improves further.

Pass 3 No value improves further.

Since $|V|=4$, we need at most $|V|-1=3$ passes.2 Final shortest distances from $S$ are:

Now compare that with a graph containing a cycle $A \to B \to C \to A$ of total weight $-1$. Then after $|V|-1$ passes, the distances around that cycle can still decrease, so the extra scan detects the negative cycle.2

Terms such as simple path, edge relaxation, and cycle weight are central to understanding why the algorithm works.2

Footnotes

1. Bellman–Ford Algorithm - GeeksforGeeks - Explains Bellman-Ford, relaxation, and negative cycle detection with the extra pass. ↩ ↩²

2. CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS - CLRS-based treatment of Bellman-Ford correctness, shortest paths, and reachable negative cycles. ↩ ↩² ↩³ ↩⁴

3. Bellman-Ford - finding shortest paths with negative weights - Provides algorithm intuition, complexity, and the criterion for negative-cycle detection. ↩ ↩²

Concise academic answer suitable for theory exams

A negative weight cycle is a cycle in a weighted directed graph whose total edge weight is negative.2 If such a cycle is reachable from the source, then the single-source shortest-distance problem has no finite solution, because repeatedly traversing the cycle decreases path cost indefinitely.2

The Bellman-Ford algorithm finds shortest distances from one source to all vertices in a directed weighted graph, even when some edges have negative weights.2 It initializes the source distance to $0$ and all others to $\\infty$, then relaxes every edge repeatedly for $|V|-1$ rounds.2 Finally, it checks all edges once more; if any distance can still be reduced, a reachable negative weight cycle exists.3

Algorithm:

1. Set $d[s]=0$ and $d[v]=\\infty$ for all $v \\ne s$.
2. Repeat $|V|-1$ times:
   • For every edge $(u,v)$, if $d[u] + w(u,v) < d[v]$, set $d[v] = d[u] + w(u,v)$.2
3. For every edge $(u,v)$, if $d[u] + w(u,v) < d[v]$, report negative weight cycle.2
4. Otherwise, output all distances.

Its time complexity is $O(|V||E|)$ and space complexity is $O(|V|)$.2

Footnotes

1. Bellman–Ford Algorithm - GeeksforGeeks - Explains Bellman-Ford, relaxation, and negative cycle detection with the extra pass. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

2. CHAPTER 25: SINGLE-SOURCE SHORTEST PATHS - CLRS-based treatment of Bellman-Ford correctness, shortest paths, and reachable negative cycles. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

3. Bellman-Ford and Floyd-Warshall 1 Single Source Shortest Path - Notes explaining why negative cycles make shortest paths ill-defined and can drive distances to negative infinity. ↩

4. Bellman-Ford - finding shortest paths with negative weights - Provides algorithm intuition, complexity, and the criterion for negative-cycle detection. ↩ ↩² ↩³