1. One-Liner
Bellman-Ford relaxes all edges up to V−1 times to propagate shortest distances; a V-th pass detects negative cycles reachable from the source.
2. The Problem It Solves
Single-source shortest paths when edges may be negative (but no negative cycle on the path you want). If a negative cycle is reachable, shortest paths are undefined (−∞).
3. The Core Idea
Any shortest path uses at most V−1 edges (simple path). Round k spreads correct distances up to k hops; after V−1 rounds, all simple paths are captured.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | dist[s]=0, others ∞ |
| 2 | Repeat V−1 times: for each edge (u,v,w), relax: dist[v]=min(dist[v], dist[u]+w) |
| 3 | One more pass: if any relax succeeds → negative cycle reachable |
| 4 | Else dist[] is shortest path distances |
5. Dry Run Example
3 vertices: 0→1 (−1), 1→2 (−2), 2→0 (2). Cycle sum = −1. Negative cycle — distances not well-defined; Bellman-Ford detects on extra relax.
Simple DAG-like chain 0→1 (3), 1→2 (4): after one round distances propagate; V−1 rounds suffice.
6. Key Properties
| Property | Value |
|---|---|
| Negative edges | Yes |
| Negative cycle detection | Yes |
| SPFA | Heuristic queue variant; worst case still bad |
7. Where It Is Used
| Domain | Use |
|---|---|
| Currency arbitrage | Negative log cycle detection |
| Network routing (historical) | Distance-vector ideas |
| Competitive programming | Small graphs with negatives |
8. Interview Tips
Contrast with Dijkstra; explain why V−1; detect cycle test. Follow-up: Floyd-Warshall for all-pairs.
9. Comparison with Other Algorithms
| Bellman-Ford | Dijkstra | |
|---|---|---|
| Neg weights | Yes | No |
| Time | O(VE) | O((V+E) log V) |
| Dense | Often OK small V | Better large sparse |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V · E) |
| Space | O(V) |
Implementation Example (PYTHON)
def bellman_ford(n, edges, src):
INF = 10**18
dist = [INF] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # negative cycle
return dist