Overview
Bellman-Ford repeatedly relaxes every edge, allowing shortest-path estimates to improve across paths with more edges. A final relaxation pass detects reachable negative cycles.
CoreSource checked
Bellman-Ford
Finds single-source shortest paths even when edges can have negative weights.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Shortest Path
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
edge relaxationnegative edge weightspass countnegative cycle detectiondistance relaxationedge weightsdynamic programminggraph representation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(VE)
Average
O(VE)
Worst
O(VE)
Space
O(V)
When to Use
- Use when negative edge weights may appear but negative cycles should be detected.
- Use when the graph is small enough for O(VE) relaxation.
When Not to Use
- Avoid when all weights are nonnegative and Dijkstra's algorithm is faster.
- Avoid when negative cycles are valid model behavior rather than an error state.
What It Does
- Computes single-source shortest paths
- Detects negative-weight cycles
Use Cases
- Graphs with negative edge weights
- Currency arbitrage checks
- Network distance-vector routing
Inputs
- Weighted graph
- Starting node
Outputs
- Shortest distances
- Negative-cycle warning
Key Formulas (1)
Relaxation step
dist[v] = min(dist[v], dist[u] + weight(u, v))
dist[v] = min(dist[v], dist[u] + weight(u, v))Repeats edge relaxation enough times to propagate shortest paths through the graph.
Pseudocode
- 1.Initialize distances from the source
- 2.Repeat V - 1 times
- 3.For each edge u->v with weight w
- 4.If dist[u] + w improves dist[v], update dist[v] and predecessor[v]
- 5.Afterward, scan edges once more
- 6.If any reachable edge can still relax, report a negative cycle
Canonical Example
- Input
- edges A->B cost 4, A->C cost 5, C->B cost -3
- Output
- dist[B] = 2 via A->C->B
- Explanation
- Repeated relaxation lets the negative edge improve the earlier direct distance to B.
Implementation Notes
- Initialize dist[source] = 0 and all other distances to infinity.
- Relax all edges V - 1 times.
- Run one more pass to flag reachable negative cycles.
Common Pitfalls
- Failing to run the extra pass misses negative-cycle detection.
- Unreachable vertices should not relax outgoing edges from infinity.
- A negative cycle matters only if it is reachable from the source.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow all edges being relaxed across repeated passes.
S
#
#
#
#
#
#
#
G
Step 1 of 6: Initialize distances from the source
edge-relaxationNotes
Bellman-Ford is slower than Dijkstra on nonnegative graphs, but it handles negative edges and detects reachable negative cycles.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Bellman-Ford.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toDijkstra's Algorithm
Bellman-Ford supports negative edge weights at higher cost.
Prerequisite ofJohnson's Algorithm
Johnson's Algorithm uses Bellman-Ford to compute reweighting potentials.
Used byJohnson's Algorithm
Johnson's Algorithm uses Bellman-Ford to compute reweighting potentials.
Related Algorithms
Tags
Shortest PathWeighted GraphDynamic ProgrammingGraph