Bellman-Ford Algorithm
Graph shortest-path algorithm
The Bellman-Ford algorithm is a graph algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted graph, correctly handling negative edge weights and detecting negative-weight cycles.
Definition
The Bellman-Ford algorithm is a graph algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted graph, correctly handling negative edge weights and detecting negative-weight cycles.
Overview
Bellman-Ford solves the single-source shortest path problem by iteratively relaxing every edge in the graph. Starting with a distance estimate of zero for the source and infinity for all other vertices, the algorithm repeats a full pass over all edges up to V-1 times (where V is the number of vertices), updating a vertex's distance whenever a shorter path is found through a given edge. Because it relaxes every edge rather than greedily picking the nearest unvisited vertex like Dijkstra's algorithm does, it tolerates negative edge weights without producing incorrect results. A key practical strength of Bellman-Ford is its ability to detect negative-weight cycles reachable from the source. After the V-1 relaxation passes, a final pass checks whether any edge can still be relaxed; if so, the graph contains a negative cycle and no shortest path is well-defined for the affected vertices. This detection capability makes Bellman-Ford useful beyond pure shortest-path computation, for example in arbitrage detection in currency exchange graphs, where a negative cycle represents a profitable trading loop. The algorithm runs in O(V * E) time, which is slower than Dijkstra's O((V + E) log V) with a priority queue, so Dijkstra is generally preferred when all edge weights are non-negative. Bellman-Ford's simplicity and edge-relaxation structure also make it naturally suited to distributed and parallel implementations, and a variant underlies the distance-vector routing protocols historically used in computer networking, such as early versions of RIP (Routing Information Protocol). The algorithm is named after Richard Bellman and Lester Ford Jr., who described it in the 1950s.
Key Concepts
- Computes single-source shortest paths in weighted directed graphs
- Correctly handles negative edge weights, unlike Dijkstra's algorithm
- Detects negative-weight cycles reachable from the source vertex
- Runs in O(V * E) time via repeated edge relaxation
- Simple to implement using a single array of distance estimates
- Naturally parallelizable and adaptable to distributed computation
- Basis for distance-vector routing protocols like early RIP
- Terminates early if a full pass produces no distance updates
Use Cases
Frequently Asked Questions
From the Blog
Feature Engineering: Turning Data Into Signal
Feature engineering turns raw columns into inputs a model can actually learn from. Learn the core techniques that often matter more than the algorithm itself.
Read More ProgrammingWhat Is Big O Notation? A Beginner Guide
Big O notation describes how an algorithm's time or memory grows as input size increases. Learn the common complexities and how to analyze your own code.
Read More Data ScienceWhat Is Feature Engineering in Machine Learning?
Feature engineering is transforming raw data into inputs that help models learn. Good features often matter more than the algorithm. Learn the core techniques here.
Read More AI & TechnologyWhat Is Gradient Descent Explained for Beginners
Gradient descent is the algorithm that trains most machine learning models by repeatedly nudging parameters in the direction that reduces error, step by step.
Read More