Bellman-Ford is the shortest-path algorithm you reach for when Dijkstra fails — specifically when graphs contain negative-weight edges or you need to detect negative cycles. It appears in finance (arbitrage detection), routing protocols (RIP), and interviews at companies asking about weighted graph problems.
When to Use Bellman-Ford vs Dijkstra
| Criterion | Dijkstra | Bellman-Ford |
|---|---|---|
| Negative edge weights | Fails (greedy assumption broken) | Handles correctly |
| Negative cycles | Cannot detect | Detects explicitly |
| Time complexity | O((V + E) log V) with min-heap | O(V * E) |
| When to use | Non-negative weights, performance-critical | Negative weights or cycle detection needed |
How Bellman-Ford Works
Key insight: any shortest path in a graph with V vertices has at most V-1 edges (if it had V or more, it would visit a vertex twice — a cycle). So we relax all edges V-1 times. After V-1 iterations, if we can still relax any edge, a negative cycle exists.
def bellman_ford(n: int, edges: list[tuple], src: int) -> tuple[list[float], bool]:
"""
Bellman-Ford shortest path from src to all vertices.
edges: list of (u, v, weight)
Returns: (dist[], has_negative_cycle)
Time: O(V * E), Space: O(V)
"""
INF = float('inf')
dist = [INF] * n
dist[src] = 0
# Relax all edges V-1 times
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # Early termination if no updates
# V-th relaxation: if anything updates, negative cycle exists
has_negative_cycle = False
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
has_negative_cycle = True
break
return dist, has_negative_cycle
# Example: graph with 5 vertices
n = 5
edges = [
(0, 1, -1),
(0, 2, 4),
(1, 2, 3),
(1, 3, 2),
(1, 4, 2),
(3, 2, 5),
(3, 1, 1),
(4, 3, -3),
]
dist, cycle = bellman_ford(n, edges, src=0)
print(f"Distances from 0: {dist}") # [0, -1, 2, -2, 1]
print(f"Negative cycle: {cycle}") # FalseReconstructing the Path
def bellman_ford_with_path(n: int, edges: list[tuple], src: int, dst: int):
"""Returns (distance, path) or (inf, []) if no path or negative cycle."""
INF = float('inf')
dist = [INF] * n
prev = [-1] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
# Check for negative cycles on the path to dst
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
return INF, [] # Negative cycle
# Reconstruct path
path = []
node = dst
while node != -1:
path.append(node)
node = prev[node]
path.reverse()
if path[0] != src:
return INF, [] # No path exists
return dist[dst], pathApplication: Currency Arbitrage Detection
Convert currency exchange rates to log space — a negative cycle in log-transformed weights means an arbitrage opportunity exists.
import math
def find_arbitrage(currencies: list[str], rates: list[list[float]]) -> bool:
"""
Detect currency arbitrage: a sequence of conversions that returns
more money than you started with.
Transform: weight = -log(rate)
Arbitrage exists ↔ negative cycle in transformed graph
"""
n = len(currencies)
edges = []
for i in range(n):
for j in range(n):
if i != j and rates[i][j] > 0:
# Negate log because Bellman-Ford finds minimum
edges.append((i, j, -math.log(rates[i][j])))
# Run Bellman-Ford from each source to catch all components
for src in range(n):
_, has_cycle = bellman_ford(n, edges, src)
if has_cycle:
return True # Arbitrage opportunity detected
return FalseSPFA (Shortest Path Faster Algorithm)
Queue-optimized Bellman-Ford — only re-relaxes nodes whose distance was just updated:
from collections import deque
def spfa(n: int, graph: list[list[tuple]], src: int) -> list[float]:
"""
SPFA: Bellman-Ford with queue optimization.
Average case much faster; worst case still O(V * E).
"""
INF = float('inf')
dist = [INF] * n
dist[src] = 0
in_queue = [False] * n
in_queue[src] = True
queue = deque([src])
while queue:
u = queue.popleft()
in_queue[u] = False
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
in_queue[v] = True
queue.append(v)
return distLeetCode Problems
- LeetCode 743: Network Delay Time (Dijkstra or Bellman-Ford)
- LeetCode 787: Cheapest Flights Within K Stops (Bellman-Ford with K limit)
- LeetCode 1334: Find the City With Smallest Number of Neighbors at Threshold (Floyd-Warshall)
K-Stop Constraint (LeetCode 787)
def find_cheapest_price(n: int, flights: list[list[int]],
src: int, dst: int, k: int) -> int:
"""
Cheapest flight from src to dst with at most k stops (k+1 edges).
Bellman-Ford limited to k+1 relaxation rounds.
"""
INF = float('inf')
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1): # At most k+1 edges = k stops
temp = dist[:] # Must copy to prevent using same-round updates
for u, v, price in flights:
if dist[u] != INF and dist[u] + price < temp[v]:
temp[v] = dist[u] + price
dist = temp
return dist[dst] if dist[dst] != INF else -1Related Graph Topics
- BFS vs DFS — Bellman-Ford is a relaxation algorithm, not a traversal; but understanding graph traversal is prerequisite for shortest path algorithms
- Minimum Spanning Tree — MST minimizes total edge weight connecting all nodes; Bellman-Ford finds shortest path from one source; related but different objectives