10.6 Detecting Negative Cycles with Bellman-Ford

In the previous recipe, Bellman-Ford was used to compute shortest paths in graphs that contain negative edge weights.

algorithmsshortest-pathsgraphs

10.6 Detecting Negative Cycles with Bellman-Ford

In the previous recipe, Bellman-Ford was used to compute shortest paths in graphs that contain negative edge weights. The algorithm included an additional pass that detected negative cycles, but the detection itself deserves a closer look.

Negative cycles are fundamentally different from ordinary graph structures. A shortest path normally represents a minimum cost route between two vertices. A negative cycle destroys that concept. If traversing a cycle decreases total cost, then repeatedly traversing the cycle decreases the path cost indefinitely.

In such graphs, shortest paths cease to exist.

This recipe focuses on identifying negative cycles and determining which vertices are affected by them.

Problem

Given a directed weighted graph, determine whether a negative cycle is reachable from the source.

For example:

A --1--> B
^         |
|         |
|         v
C <-- -4--
     1

The cycle:

A -> B -> C -> A

has total cost:

1 + (-4) + 1 = -2

Each traversal decreases the path cost by two.

No finite shortest path exists.

The goal is to detect this condition.

Solution

Bellman-Ford computes shortest paths using:

V - 1

relaxation passes.

If another improvement remains possible after those passes, a negative cycle must exist.

package main

import "fmt"

type Edge struct {
	From   int
	To     int
	Weight int
}

func hasNegativeCycle(vertices int, edges []Edge, source int) bool {
	const INF = int(1e18)

	dist := make([]int, vertices)

	for i := range dist {
		dist[i] = INF
	}

	dist[source] = 0

	for i := 0; i < vertices-1; i++ {
		for _, edge := range edges {
			if dist[edge.From] == INF {
				continue
			}

			newDistance := dist[edge.From] + edge.Weight

			if newDistance < dist[edge.To] {
				dist[edge.To] = newDistance
			}
		}
	}

	for _, edge := range edges {
		if dist[edge.From] == INF {
			continue
		}

		if dist[edge.From]+edge.Weight < dist[edge.To] {
			return true
		}
	}

	return false
}

func main() {
	edges := []Edge{
		{0, 1, 1},
		{1, 2, -4},
		{2, 0, 1},
	}

	fmt.Println(hasNegativeCycle(3, edges, 0))
}

Output:

true

Why the Detection Works

Suppose a graph contains:

0 -> 1 = 3
1 -> 2 = 2

The shortest path to vertex 2 contains at most:

V - 1

edges.

After enough relaxation passes, the optimal distance becomes known.

Further passes produce no changes.

A graph with a negative cycle behaves differently.

Consider:

0 -> 1 = 1
1 -> 2 = -3
2 -> 0 = 1

The cycle cost is:

1 + (-3) + 1 = -1

After one traversal:

distance[0] = -1

After two traversals:

distance[0] = -2

After three traversals:

distance[0] = -3

Distances continue decreasing forever.

The extra Bellman-Ford pass detects precisely this behavior.

If relaxation remains possible, some cycle must still be generating improvements.

Since all shortest paths should already have converged, that cycle must be negative.

Finding the Actual Cycle

Detecting the existence of a negative cycle is often sufficient.

Some applications require the cycle itself.

Bellman-Ford can reconstruct it by recording predecessors.

parent[edge.To] = edge.From

Whenever a relaxation occurs.

During the final pass, remember the last updated vertex.

changedVertex = edge.To

If a negative cycle exists, repeatedly following predecessors eventually enters the cycle.

A common implementation is:

for i := 0; i < vertices; i++ {
	changedVertex = parent[changedVertex]
}

After walking backward V times, the vertex must lie inside the cycle.

The cycle can then be reconstructed by continuing until the starting vertex reappears.

This technique appears frequently in competitive programming and graph-analysis systems.

Reachable Versus Unreachable Negative Cycles

A subtle detail often surprises newcomers.

Consider:

Source Component

0 -> 1 -> 2

Disconnected Component

3 -> 4 -> 5 -> 3

Suppose the disconnected component contains a negative cycle.

3 -> 4 = -1
4 -> 5 = -1
5 -> 3 = -1

Bellman-Ford starting from vertex 0 reports:

No negative cycle

Why?

Because the cycle cannot be reached from the source.

Shortest-path computation only concerns vertices reachable from the starting point.

The unreachable cycle has no effect on any path originating at the source.

This explains the guard:

if dist[edge.From] == INF {
	continue
}

Only reachable vertices participate in relaxation.

Propagating Negative Infinity

Some applications require more than cycle detection.

Consider:

A -> B -> C
     ^
     |
     D

Suppose a negative cycle reaches B.

Then:

distance[B] = -∞

Because the cycle can be traversed indefinitely.

Any vertex reachable from B also becomes:

distance = -∞

since the cycle can be repeated before continuing.

Many graph systems therefore perform an additional traversal after cycle detection.

All vertices influenced by a negative cycle are marked.

This distinction is important in:

  • Constraint solving
  • Financial arbitrage analysis
  • Program analysis
  • Route optimization systems

Discussion

Negative cycles represent inconsistencies.

In shortest-path problems, they imply that the optimization objective has no lower bound.

In financial networks, they represent arbitrage opportunities.

In constraint systems, they indicate contradictory requirements.

In scheduling systems, they often reveal invalid dependencies.

Bellman-Ford detects these inconsistencies naturally because the algorithm repeatedly attempts to improve distances.

Normal graphs eventually stabilize.

Graphs containing negative cycles do not.

This difference is the foundation of the detection mechanism.

Complexity

The detection pass adds only one extra scan of all edges.

Operation Complexity
Bellman-Ford relaxation O(VE)
Negative-cycle detection O(E)
Cycle reconstruction O(V)
Memory usage O(V)

The detection cost is negligible compared to the relaxation phase.

Common Mistakes

Do not assume every negative edge produces a negative cycle.

A graph may contain many negative edges and still have perfectly valid shortest paths.

Do not confuse a negative cycle with a cycle whose total weight is zero.

A zero-cost cycle does not cause distances to decrease indefinitely.

Do not remove the reachability check.

Unreachable negative cycles should not influence source-based shortest-path calculations.

Do not stop after detecting a cycle if downstream vertices must be identified. Additional propagation may be required.

Practical Applications

Negative-cycle detection appears in:

  • Currency arbitrage systems
  • Foreign-exchange trading networks
  • Difference constraint systems
  • Task scheduling validation
  • Transportation optimization
  • Resource allocation systems
  • Compiler data-flow analysis
  • Graph consistency checking

In many of these domains, discovering the inconsistency is more valuable than computing shortest paths.

Takeaway

A negative cycle indicates that path costs can decrease without bound. Bellman-Ford detects this condition by performing one additional relaxation pass after shortest paths should already have converged. If any edge can still improve a distance, a reachable negative cycle exists. This simple observation transforms Bellman-Ford from a shortest-path algorithm into a powerful graph validation tool.