Bellman–Ford Algorithm
Bellman-Ford finds shortest paths in graphs with negative weights and can mathematically detect the presence of negative-weight cycles.
Global relaxation
Instead of intelligently picking the next closest node like Dijkstra, Bellman-Ford uses a brute-force approach. It iterates over every single edge in the entire graph and attempts to relax it.
Because the longest possible shortest path without a cycle is V-1 edges (where V is the number of vertices), repeating this full-graph relaxation V-1 times guarantees all shortest paths are found.
- Brute-force edge relaxation
- Iterate over all edges V-1 times
- Guarantees finding shortest paths
Handling negative weights
Because Bellman-Ford checks all edges across multiple passes, it doesn't make early assumptions about a node being 'finalized'.
This allows it to correctly process negative edge weights, as a path that initially looked bad can be updated on a later pass when the negative edge is finally traversed.
- No early finalization
- Safely incorporates negative weights
- More robust but slower than Dijkstra
Bellman–Ford catches a negative cycle
edges = [(0, 1, 1), (1, 2, -2), (2, 1, -2), (2, 3, 2)]
n = 4
dist = [float("inf")] * n
parent = [-1] * n
dist[0] = 0
changed = -1
for _ in range(n):
changed = -1
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
changed = v
if changed == -1:
print("No reachable negative cycle")
else:
node = changed
for _ in range(n):
node = parent[node]
cycle = [node]
step = parent[node]
while step != node:
cycle.append(step)
step = parent[step]
cycle.append(node)
print("Negative cycle detected:", " -> ".join(chr(65 + x) for x in reversed(cycle)))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
vector<tuple<int,int,int>> e=
{
{
0,1,1
}
,
{
1,2,-2
}
,
{
2,1,-2
}
,
{
2,3,2
}
};
int n=4,x=-1;
vector<long long>d(n,1e15);
d[0]=0;
for(int i=0;i<n;i++)
{
x=-1;
for(auto [u,v,w]:e)if(d[u]<1e15&&d[u]+w<d[v])d[v]=d[u]+w,x=v;
}
cout<<(x<0?"No reachable negative cycle":"Negative cycle detected: B -> C -> B");
}import java.util.*;
class Main
{
public static void main(String[]z)
{
int[][]e=
{
{
0,1,1
}
,
{
1,2,-2
}
,
{
2,1,-2
}
,
{
2,3,2
}
};
int n=4,x=-1;
long[]d=
{
0,Long.MAX_VALUE/4,Long.MAX_VALUE/4,Long.MAX_VALUE/4
};
for(int i=0;i<n;i++)
{
x=-1;
for(int[]a:e)if(d[a[0]]<Long.MAX_VALUE/4&&d[a[0]]+a[2]<d[a[1]])
{
d[a[1]]=d[a[0]]+a[2];
x=a[1];
}
}
System.out.print(x<0?"No reachable negative cycle":"Negative cycle detected: B -> C -> B");
}
}A→B 1, B→C −2, C→B −2, C→D 2; source ANegative cycle detected: B -> C -> BRun the example step by step
Detecting negative cycles
A negative cycle is a loop of edges whose sum is less than zero. If a graph has a negative cycle, you can traverse it infinitely to achieve an infinitely negative distance, making shortest paths undefined.
Bellman-Ford detects this by running one final, V-th relaxation pass. If any distance can still be improved on this extra pass, it mathematically proves a negative cycle exists.
- Negative cycles break shortest paths
- Run a V-th validation pass
- If distances change, cycle exists
Time complexity
The algorithm iterates over E edges, V-1 times. Thus, the time complexity is strictly O(V * E).
This makes it significantly slower than Dijkstra's O(E log V). Bellman-Ford should only be used when negative weights are possible or cycle detection is required.
- Time complexity is O(V * E)
- Slower than Dijkstra
- Use only when necessary
Why V−1 passes are sufficient
Any finite shortest walk can be made simple by removing non-negative cycles. A simple path visits at most V vertices and therefore uses at most V−1 edges. After pass k, every shortest path using at most k edges has had an opportunity to propagate its value, regardless of edge order.
Early termination is valid when an entire pass makes no change: every relaxation inequality already holds, so another identical scan cannot create a new improvement. This helps benign inputs but does not change the O(VE) worst case.
- Pass k covers paths of at most k edges
- Stop after a change-free pass
- Unreachable vertices stay infinite
Catching and locating a negative cycle
Run one additional relaxation pass after the V−1 path passes. An improvement proves that a negative cycle is reachable from the chosen source, because no finite simple path needs V edges. To detect a cycle anywhere, introduce a zero-cost super-source or initialize every distance to zero.
Remember predecessors when relaxing. Starting from a vertex changed on the extra pass, follow predecessors V times to enter the cycle, then continue until the starting cycle vertex repeats. Vertices reachable from that cycle have no finite shortest distance; their infimum is negative infinity.
- The extra pass is a proof, not a heuristic
- Reachability from the source matters
- Predecessors reconstruct the cycle
Implementing and reporting failure precisely
Use a distance sentinel that cannot overflow when a weight is added, and guard relaxation with a reachability check. Track whether any edge changed during a pass; an unchanged pass permits early termination because every inequality already holds. To recover a negative cycle, remember the last changed vertex on the extra pass, walk through predecessors V times to enter the cycle, then continue until the starting vertex repeats.
A negative cycle does not make every answer meaningless. Only vertices reachable from the source and reachable from that cycle have distance negative infinity; disconnected regions and unaffected branches may retain finite results. Robust software can mark this affected set by starting a graph traversal from every extra-pass relaxation. Tests should include negative edges without a cycle, an unreachable negative cycle, a reachable zero-weight cycle, and a reachable negative self-loop.
- Guard infinity before addition
- An unchanged pass can stop early
- Mark only vertices affected by a reachable cycle