Bellman-Ford Algorithm
Single-source shortest path algorithm handling negative edge weights, unlike Dijkstra. Can detect negative cycles. Named after Richard Bellman and Lester Ford Jr. Essential for networks with varying costs including negative values.
Visualization
Interactive visualization for Bellman-Ford Algorithm
Bellman-Ford Algorithm
• Time: O(VE)
• Handles negative edge weights
• Detects negative cycles
Interactive visualization with step-by-step execution
Implementation
1function bellmanFord(edges: [number, number, number][], n: number, start: number): number[] | null {
2 const distances = new Array(n).fill(Infinity);
3 distances[start] = 0;
4
5 for (let i = 0; i < n - 1; i++) {
6 for (const [u, v, weight] of edges) {
7 if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
8 distances[v] = distances[u] + weight;
9 }
10 }
11 }
12
13 for (const [u, v, weight] of edges) {
14 if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
15 return null;
16 }
17 }
18 return distances;
19}Deep Dive
Theoretical Foundation
Bellman-Ford Algorithm relaxes all edges V-1 times to find shortest paths from a source to all vertices. The key insight is that after i iterations, shortest paths with at most i edges are correctly computed. Since any shortest path has at most V-1 edges (without cycles), V-1 iterations suffice. The algorithm performs edge relaxation: if dist[u] + weight(u,v) < dist[v], update dist[v]. After V-1 iterations, if any distance can still be reduced, a negative cycle exists (distances keep decreasing indefinitely). Unlike Dijkstra, which fails with negative weights, Bellman-Ford handles them correctly but is slower O(VE) vs O((V+E)log V). The algorithm is simple, works in distributed systems, and forms the basis for distance-vector routing protocols like RIP.
Complexity
Time
O(VE)
O(VE)
O(VE)
Space
O(V)
Applications
Industry Use
Currency arbitrage detection in forex markets
Network routing with varying costs (RIP protocol)
Detecting negative cycles in financial systems
Distance vector routing protocols (Internet routing)
Game theory and Nash equilibrium computation
Scheduling with penalties and bonuses
Resource allocation with negative costs
Finding arbitrage opportunities in trading
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.