Bellman-Ford Algorithm: Negative Weight Shortest Path
Dijkstra's algorithm operates on a greedy assumption: once you've found the shortest path to a node, you're done with it. This works beautifully when all edges are non-negative because adding more...
Key Insights
- Bellman-Ford handles negative edge weights where Dijkstra fails, making it essential for financial modeling, network routing with penalties, and any graph where edges can represent losses or costs that reduce totals.
- The algorithm’s V-1 iteration guarantee stems from the simple fact that the longest possible shortest path contains at most V-1 edges—any more would create a cycle.
- Negative cycle detection isn’t just a safety feature; it’s a powerful tool for finding arbitrage opportunities in currency markets and detecting inconsistencies in constraint systems.
Why Dijkstra Falls Apart with Negative Weights
Dijkstra’s algorithm operates on a greedy assumption: once you’ve found the shortest path to a node, you’re done with it. This works beautifully when all edges are non-negative because adding more edges can only increase path length. But introduce a negative edge, and that assumption crumbles.
Consider a simple graph where node A connects to B with weight 5, and B connects to C with weight -10. Dijkstra might finalize the path to B as 5, never considering that going through C and back (if such a path exists) could yield a shorter distance. The algorithm marks nodes as “visited” and moves on, missing potentially shorter paths that emerge later.
Bellman-Ford takes a different approach: it considers every edge, repeatedly, until it’s mathematically certain it has found all shortest paths. This brute-force strategy costs O(V × E) time compared to Dijkstra’s O((V + E) log V), but it’s the price of correctness when negative weights enter the picture.
Real-world applications abound. Currency exchange rates naturally create negative-weight scenarios when converted to logarithms (more on this later). Network routing protocols like RIP use distance-vector algorithms based on Bellman-Ford. Game AI pathfinding with terrain bonuses, financial transaction networks with fees and rebates, and constraint satisfaction problems all benefit from this algorithm.
Core Algorithm Mechanics
The heart of Bellman-Ford is edge relaxation. For each edge (u, v) with weight w, we check if the path to v through u is shorter than our current best:
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
The algorithm performs this relaxation on every edge, V-1 times. Why V-1? Because the shortest path between any two nodes in a graph with V vertices contains at most V-1 edges. If it contained more, we’d be revisiting a node, creating a cycle. In a graph without negative cycles, cycles never help (they either add positive weight or zero), so optimal paths are acyclic.
In the first iteration, we find all shortest paths using at most 1 edge. In the second, paths using at most 2 edges. By iteration V-1, we’ve covered all possible shortest path lengths.
Here’s the basic implementation:
from typing import List, Tuple, Dict
from math import inf
def bellman_ford(
vertices: int,
edges: List[Tuple[int, int, float]],
source: int
) -> Dict[int, float]:
"""
Basic Bellman-Ford implementation.
Args:
vertices: Number of vertices (0 to vertices-1)
edges: List of (from, to, weight) tuples
source: Starting vertex
Returns:
Dictionary mapping vertex to shortest distance from source
"""
# Initialize distances
distance = {v: inf for v in range(vertices)}
distance[source] = 0
# Relax all edges V-1 times
for _ in range(vertices - 1):
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
return distance
# Example usage
edges = [
(0, 1, 4),
(0, 2, 5),
(1, 2, -3),
(2, 3, 4),
(1, 3, 6)
]
distances = bellman_ford(4, edges, 0)
print(distances) # {0: 0, 1: 4, 2: 1, 3: 5}
Notice how vertex 2’s shortest distance is 1 (going through vertex 1 with the -3 edge), not 5 (the direct edge). Dijkstra would have finalized vertex 2 at distance 5 before discovering the better path.
Negative Cycle Detection
A negative cycle is a path that starts and ends at the same vertex with a total weight less than zero. These cycles break the concept of “shortest path” entirely—you could traverse the cycle infinitely, reducing your path length without bound.
Bellman-Ford detects negative cycles elegantly: after V-1 iterations, run one more. If any edge can still be relaxed, a negative cycle exists. Why? Because V-1 iterations are sufficient for all shortest paths in a cycle-free graph. If we can still improve, we’re exploiting a negative cycle.
from typing import List, Tuple, Dict, Set, Optional
from math import inf
def bellman_ford_with_cycle_detection(
vertices: int,
edges: List[Tuple[int, int, float]],
source: int
) -> Tuple[Optional[Dict[int, float]], Set[int]]:
"""
Bellman-Ford with negative cycle detection.
Returns:
Tuple of (distances dict or None if cycle exists,
set of vertices affected by negative cycles)
"""
distance = {v: inf for v in range(vertices)}
distance[source] = 0
predecessor = {v: None for v in range(vertices)}
# Standard V-1 relaxations
for _ in range(vertices - 1):
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
predecessor[v] = u
# V-th iteration: detect negative cycles
affected_by_cycle = set()
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
# Found a negative cycle - trace back to find all affected nodes
affected_by_cycle.add(v)
# Mark all nodes reachable from v as affected
visited = set()
current = v
while current is not None and current not in visited:
visited.add(current)
affected_by_cycle.add(current)
current = predecessor[current]
if affected_by_cycle:
# Propagate: any node reachable from cycle has undefined shortest path
# Run additional iterations to find all affected nodes
for _ in range(vertices):
for u, v, weight in edges:
if u in affected_by_cycle:
affected_by_cycle.add(v)
return (None if affected_by_cycle else distance, affected_by_cycle)
# Example with negative cycle
edges_with_cycle = [
(0, 1, 1),
(1, 2, -1),
(2, 3, -1),
(3, 1, -1), # Creates negative cycle: 1 -> 2 -> 3 -> 1 = -3
(2, 4, 2)
]
result, affected = bellman_ford_with_cycle_detection(5, edges_with_cycle, 0)
print(f"Result: {result}") # None
print(f"Affected vertices: {affected}") # {1, 2, 3, 4}
Implementation Deep Dive
For Bellman-Ford, edge list representation is natural—we iterate over all edges anyway. Adjacency lists work too but offer no advantage here, unlike in Dijkstra where we need efficient neighbor lookup.
Path reconstruction requires tracking predecessors:
from typing import List, Tuple, Dict, Optional
from math import inf
class BellmanFord:
"""Full Bellman-Ford implementation with path reconstruction."""
def __init__(self, vertices: int):
self.vertices = vertices
self.edges: List[Tuple[int, int, float]] = []
def add_edge(self, u: int, v: int, weight: float) -> None:
self.edges.append((u, v, weight))
def find_shortest_paths(
self, source: int
) -> Tuple[Dict[int, float], Dict[int, Optional[int]], bool]:
"""
Find shortest paths from source.
Returns:
(distances, predecessors, has_negative_cycle)
"""
distance = {v: inf for v in range(self.vertices)}
predecessor: Dict[int, Optional[int]] = {v: None for v in range(self.vertices)}
distance[source] = 0
# V-1 relaxations
for i in range(self.vertices - 1):
updated = False
for u, v, weight in self.edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
predecessor[v] = u
updated = True
# Early termination optimization
if not updated:
break
# Check for negative cycles
has_negative_cycle = False
for u, v, weight in self.edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
has_negative_cycle = True
break
return distance, predecessor, has_negative_cycle
def reconstruct_path(
self,
predecessor: Dict[int, Optional[int]],
target: int
) -> Optional[List[int]]:
"""Reconstruct path from source to target."""
if predecessor.get(target) is None and target != 0:
return None # No path exists
path = []
current: Optional[int] = target
visited = set()
while current is not None:
if current in visited:
return None # Cycle detected
visited.add(current)
path.append(current)
current = predecessor[current]
return list(reversed(path))
# Usage example
graph = BellmanFord(5)
graph.add_edge(0, 1, 6)
graph.add_edge(0, 2, 7)
graph.add_edge(1, 2, 8)
graph.add_edge(1, 3, -4)
graph.add_edge(1, 4, 5)
graph.add_edge(2, 3, 9)
graph.add_edge(2, 4, -3)
graph.add_edge(3, 0, 2)
graph.add_edge(4, 3, 7)
distances, predecessors, has_cycle = graph.find_shortest_paths(0)
print(f"Distances: {distances}")
print(f"Path to 3: {graph.reconstruct_path(predecessors, 3)}")
Optimizations and Variants
The early termination optimization shown above can dramatically improve average-case performance. If an iteration produces no relaxations, we’re done—no future iteration will either.
SPFA (Shortest Path Faster Algorithm) takes optimization further by maintaining a queue of vertices whose distances changed. Instead of checking all edges, we only check edges from recently updated vertices:
from collections import deque
from typing import List, Tuple, Dict
from math import inf
def spfa(
vertices: int,
adj: Dict[int, List[Tuple[int, float]]],
source: int
) -> Tuple[Dict[int, float], bool]:
"""
SPFA: Queue-based Bellman-Ford optimization.
Args:
vertices: Number of vertices
adj: Adjacency list {vertex: [(neighbor, weight), ...]}
source: Starting vertex
Returns:
(distances, has_negative_cycle)
"""
distance = {v: inf for v in range(vertices)}
distance[source] = 0
in_queue = {v: False for v in range(vertices)}
count = {v: 0 for v in range(vertices)} # Times vertex entered queue
queue = deque([source])
in_queue[source] = True
count[source] = 1
while queue:
u = queue.popleft()
in_queue[u] = False
for v, weight in adj.get(u, []):
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
count[v] += 1
# Negative cycle detection: vertex entered queue V times
if count[v] >= vertices:
return distance, True
return distance, False
SPFA averages O(E) time on random graphs but degrades to O(V × E) worst-case. Use it when you expect sparse graphs without pathological structure.
Bellman-Ford vs Dijkstra: Decision Guide
| Factor | Dijkstra | Bellman-Ford |
|---|---|---|
| Time Complexity | O((V + E) log V) | O(V × E) |
| Negative Weights | No | Yes |
| Negative Cycle Detection | No | Yes |
| Distributed Implementation | Complex | Simple |
| Space Complexity | O(V) | O(V) |
Use Dijkstra when: All weights are non-negative and performance matters. This covers most pathfinding scenarios.
Use Bellman-Ford when: Negative weights exist, you need cycle detection, or you’re implementing a distributed routing protocol where simplicity trumps speed.
Practical Application: Currency Arbitrage Detector
Currency arbitrage exploits exchange rate discrepancies. If USD → EUR → GBP → USD yields more than 1 USD, profit exists. We model this as a graph problem by taking logarithms of exchange rates, converting multiplication to addition and making arbitrage detection equivalent to finding negative cycles.
from typing import Dict, List, Tuple, Optional
from math import log, inf
def detect_arbitrage(
rates: Dict[str, Dict[str, float]]
) -> Optional[List[str]]:
"""
Detect currency arbitrage opportunities.
Args:
rates: Exchange rates {from_currency: {to_currency: rate}}
rate means 1 unit of from_currency = rate units of to_currency
Returns:
Arbitrage cycle as list of currencies, or None
"""
currencies = list(rates.keys())
n = len(currencies)
currency_index = {c: i for i, c in enumerate(currencies)}
# Build edge list with -log(rate) weights
# Negative cycle in -log space = profitable cycle in rate space
edges: List[Tuple[int, int, float]] = []
for from_curr, to_rates in rates.items():
for to_curr, rate in to_rates.items():
if rate > 0:
edges.append((
currency_index[from_curr],
currency_index[to_curr],
-log(rate)
))
# Run Bellman-Ford from each vertex to find any negative cycle
for source in range(n):
distance = [inf] * n
predecessor = [-1] * n
distance[source] = 0
# V-1 relaxations
for _ in range(n - 1):
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
predecessor[v] = u
# Check for negative cycle
for u, v, weight in edges:
if distance[u] != inf and distance[u] + weight < distance[v]:
# Found negative cycle - reconstruct it
cycle = []
visited = [False] * n
current = v
# Get into the cycle
for _ in range(n):
current = predecessor[current]
# Trace the cycle
start = current
while True:
cycle.append(currencies[current])
current = predecessor[current]
if current == start:
cycle.append(currencies[current])
break
return list(reversed(cycle))
return None
# Example usage
exchange_rates = {
'USD': {'EUR': 0.92, 'GBP': 0.79, 'JPY': 149.50},
'EUR': {'USD': 1.09, 'GBP': 0.86, 'JPY': 162.80},
'GBP': {'USD': 1.27, 'EUR': 1.17, 'JPY': 189.50},
'JPY': {'USD': 0.0067, 'EUR': 0.0062, 'GBP': 0.0053}
}
arbitrage = detect_arbitrage(exchange_rates)
if arbitrage:
print(f"Arbitrage opportunity: {' -> '.join(arbitrage)}")
else:
print("No arbitrage opportunity found")
This implementation converts the multiplicative nature of exchange rates into an additive graph problem. A cycle where the product of rates exceeds 1 becomes a negative cycle in log-space, which Bellman-Ford detects naturally.
Bellman-Ford may be slower than Dijkstra, but when negative weights enter the picture, it’s not just the better choice—it’s the only correct one.