Bellman-Ford Algorithm
Learn how to find the shortest paths in graphs that may contain negative weight edges, and how to detect negative weight cycles.
Ready to start
Status
Current Iteration: 0
| Node | Distance |
|---|---|
| No Data | |
Speed
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Unlike Dijkstra, which aggressively chooses the shortest known path, Bellman-Ford is cautious.
It assumes any path could be improved by any edge, so it iteratively checks all edges to see if they can offer a shortcut.
This careful approach allows it to handle negative edge weights.
Concept
- Relaxation: Checking if an edge (u, v) with weight w allows us to reach v cheaper than before (dist[v] > dist[u] + w).
- V-1 Iterations: In a graph with V nodes, the longest simple path can have at most V-1 edges. Repeating relaxation V-1 times guarantees finding shortest simple paths.
- Negative Cycle: If we can still relax an edge after V-1 iterations, it means there's a cycle that reduces total distance forever (Negative Cycle).
How it Works
Algorithm Steps:
- Initialize distances:
dist[start] = 0, others = ∞. - Repeat
V-1times:- Iterate through all edges (u, v, w).
- If
dist[u] + w < dist[v], updatedist[v] = dist[u] + w.
- Check for Negative Cycles:
- Iterate through all edges one more time.
- If any edge can still be relaxed, a negative cycle exists.
Step-by-Step Breakdown
Watch the visualization:
- Emerald Edge: Currently checking if this edge improves the distance.
- Orange Node: Node has a finite distance from start.
- Red Edge: Part of a detected negative cycle.
When to Use
Use Bellman-Ford when:
- The graph contains negative edge weights.
- You need to detect negative cycles (e.g., currency arbitrage).
- The graph is small enough (O(VE) is slower than Dijkstra O(E log V)).
When NOT to Use
- Positive Weights Only: Dijkstra's is significantly faster.
- Large Graphs: O(VE) complexity makes it impractical for very large networks.
How to Identify
"Shortest path with negative weights", "Detect negative cycle", "Arbitrage opportunities".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.