Algorithms
Bellman-Ford: Negative Weights and Cycles
Цели урока
- Understand when Dijkstra fails
- Implement Bellman-Ford
- Detect negative cycles
- Know applications: RIP, arbitrage
Предварительные знания
- Dijkstra's algorithm
Dijkstra is fast but fragile: one negative edge breaks it. Bellman-Ford is slower but rock-solid, and even finds 'infinitely short' paths through negative cycles.
- RIP routing protocol
- Currency arbitrage on financial markets
- Constraint systems in scheduling
- Dependency analysis (make, compilers)
Three names on one algorithm
Bellman-Ford carries two names, but at least three people have a real claim to it. Richard Bellman published it in 1958 in the Quarterly of Applied Mathematics, and it fit naturally into his broader work on dynamic programming, a term Bellman himself coined while at RAND. Lester Ford Jr. had described the same relaxation idea in a 1956 RAND report on network flow, two years earlier. And Edward F. Moore, the same Moore behind BFS, published an equivalent method in 1957 for routing, which is why the algorithm is sometimes called Bellman-Ford-Moore. The shared core is simple and robust: relax every edge V-1 times and the shortest distances are guaranteed to settle, with no assumption that weights are non-negative. That tolerance for negative edges is exactly what Dijkstra lacks, and it is what lets one extra relaxation pass detect a negative cycle. The method became the backbone of distance-vector routing, including the early RIP protocol, where its 'count to infinity' weakness drove later fixes like split horizon.
Idea: Relax All Edges
**Dijkstra's problem:** the greedy choice locks in a vertex, but a negative edge may later improve the path.
**Bellman-Ford's solution:** don't lock vertices at all. Simply do V-1 passes over ALL edges and improve distances.
**Why V-1 iterations?**
**Bellman-Ford is simpler than Dijkstra:** no priority queue, just V-1 passes over all edges.
Why does Bellman-Ford do exactly V-1 iterations?
Implementation
| Algorithm | Complexity | Negative weights |
|---|---|---|
| Dijkstra (heap) | O((V+E) log V) | NO |
| Bellman-Ford | O(VE) | YES |
| Floyd-Warshall | O(V³) | YES (all pairs) |
**O(VE)** - slower than Dijkstra. Use Bellman-Ford only when there are negative weights.
Graph with V=100, E=1000. How many times slower is Bellman-Ford than Dijkstra?
Negative Cycle Detection
**Negative cycle** - a cycle with a negative sum of weights. The path can be improved infinitely by going around the cycle.
**Currency arbitrage:** if there's a cycle USD→EUR→JPY→USD with product > 1, you can grow money infinitely. Taking the logarithm turns multiplication into addition, and this becomes a negative cycle!
How does Bellman-Ford detect a negative cycle?
Applications
**1. Routing (RIP protocol):**
**2. Currency arbitrage:**
**3. Difference constraints system:**
If Bellman-Ford finishes without flagging a negative cycle, every distance in the returned array is the true shortest path - period.
When a negative cycle is reachable from the source, distances to vertices downstream of that cycle are not well-defined (they tend to negative infinity). Only vertices whose shortest path does NOT pass through a negative cycle have valid dist values.
The algorithm formally returns a dist array after V-1 iterations and the numbers look authoritative. In reality they reflect the best path of at most V-1 edges, not a true shortest path when an infinitely-decreasing cycle sits in the way.
Currency arbitrage is a search for:
Bellman-Ford
- V-1 iterations of relaxing all edges
- Works with negative weights
- Detects negative cycles
- O(VE) - slower than Dijkstra
- Use only when negative weights are present
Вопросы для размышления
- Edge relaxation V-1 times is exactly the DP transition dp[v] = min(dp[u] + w). Which other familiar algorithms amount to plain 'brute relaxation' applied enough times to converge?
- Why does RIP suffer from 'count to infinity' even though Bellman-Ford is mathematically correct - what changes when a centralized algorithm becomes distributed across routers?
- Currency arbitrage via -log(rate) is the canonical example of turning multiplication into addition via logarithms. Where else does this trick reappear, and why is it so universally effective?
Related Topics
Bellman-Ford is the foundation for other algorithms.
- Dijkstra — Faster for non-negative weights
- Floyd-Warshall — All-pairs shortest paths
- SPFA — Bellman-Ford optimization
Связанные уроки
- alg-14-dijkstra — Dijkstra is faster but no negative edges
- alg-16-floyd — Floyd-Warshall is all-pairs version of the same problem
- alg-12-bfs — BFS solves SSSP for unit weights - the baseline
- alg-21-dp — Bellman-Ford is DP on graph: relaxation = DP transition
- prob-12-lln — V-1 iterations guarantee convergence like LLN
- prob-04-bayes
- ds-16-graphs-intro