10.5 Detecting Negative Edges with Bellman-Ford

Dijkstra's algorithm depends on a crucial assumption: edge weights must be nonnegative. Once negative edges enter the graph, the greedy strategy that makes Dijkstra efficient no longer works. A path that appears optimal today may become cheaper tomorrow through a negative-weight edge discovered later.

Bellman-Ford takes a different approach. Instead of greedily finalizing distances, it repeatedly relaxes every edge in the graph until no further improvements are possible.

This approach is slower than Dijkstra, but it provides two capabilities that Dijkstra cannot:

• It correctly handles negative edge weights.
• It detects negative cycles.

Whenever a graph may contain negative costs, Bellman-Ford becomes the standard solution.

Problem

Given a weighted directed graph that may contain negative edge weights, compute the shortest distance from a source vertex to every other vertex.

Additionally, detect whether a negative cycle is reachable from the source.

Consider the graph:

A --4--> B
|         ^
|         |
2         |
|         |
v         |
C --- -3--

Starting from A, the shortest path to B is not the direct edge.

Instead:

A -> C -> B

has cost:

2 + (-3) = -1

A shortest-path algorithm must discover this improvement.

Solution

Bellman-Ford repeatedly relaxes every edge.

If a graph contains V vertices, the algorithm performs at most V - 1 complete relaxation passes.

package main

import "fmt"

type Edge struct {
	From   int
	To     int
	Weight int
}

func bellmanFord(vertices int, edges []Edge, source int) ([]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++ {
		updated := false

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

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

			if newDistance >= dist[edge.To] {
				continue
			}

			dist[edge.To] = newDistance
			updated = true
		}

		if !updated {
			break
		}
	}

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

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

	return dist, false
}

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

	dist, hasNegativeCycle := bellmanFord(3, edges, 0)

	fmt.Println(dist)
	fmt.Println(hasNegativeCycle)
}

Output:

[0 -1 2]
false

The shortest path to vertex 1 has cost -1.

Understanding Edge Relaxation

Bellman-Ford is built entirely around one operation:

if dist[u]+weight < dist[v] {
	dist[v] = dist[u] + weight
}

This operation asks:

Can I reach v more cheaply through u?

Suppose we know:

distance[A] = 5

and we have:

A --2--> B

Then:

distance[B]

can potentially become:

5 + 2 = 7

If the current value for B is larger than 7, we improve it.

Every shortest-path algorithm in this chapter relies on this same idea.

The difference is how often and in what order relaxations occur.

Why V - 1 Passes Are Enough

A shortest path cannot contain more than:

V - 1

edges.

If a path contained:

V

or more edges, some vertex would appear twice.

That repeated vertex would form a cycle.

Removing the cycle produces a shorter or equal path.

Therefore, every shortest path can be represented using at most:

V - 1

edges.

After one pass, Bellman-Ford finds all shortest paths that use one edge.

After two passes, it finds all shortest paths that use two edges.

After:

V - 1

passes, every shortest path has been discovered.

Visualizing the Process

Consider:

0 --6--> 1
0 --7--> 2
1 --5--> 3
2 --8--> 3
2 --(-3)-> 4
4 --2--> 3

Initially:

[0 ∞ ∞ ∞ ∞]

After the first pass:

[0 6 7 4 4]

After the second pass:

[0 6 7 4 4]

No distances improve.

The algorithm terminates early.

The shortest paths are already known.

Detecting Negative Cycles

Bellman-Ford provides something Dijkstra cannot.

Suppose we have:

A -> B = 1
B -> C = -3
C -> A = 1

The cycle cost is:

1 + (-3) + 1 = -1

Every trip around the cycle reduces total cost.

0
-1
-2
-3
-4
...

No shortest path exists because the cost can decrease forever.

Bellman-Ford detects this situation naturally.

After completing:

V - 1

passes, every shortest path should already be known.

If one additional relaxation still improves a distance:

if dist[u] + weight < dist[v]

then some negative cycle must exist.

That observation produces the final detection pass.

Early Termination

Many real-world graphs converge long before:

V - 1

passes.

The implementation tracks whether any update occurred.

updated := false

If a pass completes without improvements:

if !updated {
	break
}

the algorithm terminates immediately.

This optimization often reduces runtime substantially.

Discussion

Bellman-Ford and Dijkstra solve the same mathematical problem but rely on different assumptions.

Dijkstra assumes:

No negative edge weights.

Bellman-Ford assumes:

Nothing about edge signs.

Dijkstra gains efficiency through a greedy invariant.

Bellman-Ford gains generality through exhaustive relaxation.

This difference explains their performance characteristics.

Dijkstra explores vertices.

Bellman-Ford explores edges.

Complexity

Let:

• V = number of vertices
• E = number of edges

Bellman-Ford performs:

(V - 1) × E

relaxations.

Operation	Complexity
Relaxation pass	O(E)
Total passes	O(V)
Total runtime	O(VE)
Memory usage	O(V)

Compared to Dijkstra:

Algorithm	Negative Edges	Negative Cycles	Complexity
BFS	No	No	O(V + E)
Dijkstra	No	No	O((V + E) log V)
Bellman-Ford	Yes	Yes	O(VE)

Bellman-Ford is slower, but it solves a more general problem.

Common Mistakes

Do not run Dijkstra on graphs with negative edges and assume it will "usually work." The failure may be subtle and data dependent.

Do not stop after the first relaxation pass. Improvements often propagate gradually through the graph.

Do not forget to check for unreachable vertices before performing arithmetic with infinity values.

if dist[u] == INF {
	continue
}

Without this check, overflow may occur.

Do not confuse a negative edge with a negative cycle. Negative edges are perfectly valid. Negative cycles are what make shortest paths undefined.

Practical Applications

Bellman-Ford appears in several important systems:

• Currency arbitrage detection
• Financial trading networks
• Routing protocols such as RIP
• Constraint systems
• Difference constraints
• Dependency analysis
• Graph validation tools

Many of these applications depend on negative-cycle detection rather than shortest-path computation itself.

Takeaway

Bellman-Ford replaces Dijkstra's greedy selection rule with repeated edge relaxation. This allows it to handle negative edge weights and detect negative cycles. The algorithm is slower than Dijkstra, but its ability to solve a broader class of shortest-path problems makes it an essential tool whenever edge costs may become negative.