What is the Bellman-Ford Algorithm?
Learn how the Bellman-Ford algorithm finds shortest paths with negative weights and detects negative cycles, with a clear answer breakdown.
Expected Interview Answer
Bellman-Ford finds shortest paths from a single source to every other vertex in a weighted graph by relaxing all edges repeatedly for V-1 rounds, and unlike Dijkstra it correctly handles negative edge weights and can detect negative-weight cycles.
The algorithm initializes the source distance to zero and every other vertex to infinity, then for V-1 iterations it walks every edge and updates a vertex's distance if going through that edge gives a shorter path, a process called relaxation. Because any shortest path in a graph with V vertices has at most V-1 edges, V-1 full passes are guaranteed to converge on the true shortest distances if none exist. A final extra pass checks whether any edge can still be relaxed; if so, the graph contains a negative-weight cycle reachable from the source and no shortest path is well-defined. This tradeoff of O(V * E) time versus Dijkstra's O(E log V) is the price paid for correctness on graphs with negative weights, which makes Bellman-Ford the standard choice for currency arbitrage detection and network routing protocols like RIP.
- Correctly handles negative edge weights
- Detects negative-weight cycles reachable from the source
- Simple edge-relaxation loop, easy to reason about
- Works on any weighted directed graph
AI Mentor Explanation
A team manager tracking the cheapest way to fly a player from the home city to every ground on tour re-checks every scheduled flight leg V-1 times, updating a city's best-known travel cost whenever a leg offers a cheaper route through it. Some legs might carry a rebate that effectively lowers total cost, acting like a negative weight, and the manager must keep re-scanning because a rebate discovered late can still improve an already-recorded cost. After V-1 full scans every city's true cheapest cost is locked in, since no route needs more than V-1 legs. One more scan is run purely as a check; if any city's cost still drops, the schedule contains a rebate loop that never stops paying out, which is the cricket-board equivalent of a negative cycle.
Step-by-Step Explanation
Step 1
Initialize distances
Set the source distance to 0 and every other vertex to infinity.
Step 2
Relax every edge, V-1 times
For each of V-1 passes, walk every edge and update dist[v] if dist[u] + weight(u,v) is smaller.
Step 3
Run one extra relaxation pass
If any edge can still be relaxed after V-1 passes, a negative-weight cycle exists reachable from the source.
Step 4
Report results
Otherwise the recorded distances are the true shortest paths from the source to every vertex.
What Interviewer Expects
- State the O(V * E) time complexity and why V-1 passes suffice
- Explain that it handles negative edge weights, unlike Dijkstra
- Describe the extra pass used to detect negative-weight cycles
- Give a real use case: currency arbitrage or distance-vector routing (RIP)
Common Mistakes
- Confusing Bellman-Ford with Dijkstra and claiming it needs non-negative weights
- Forgetting the extra V-th pass that detects negative cycles
- Assuming it works on graphs with a negative cycle by returning some finite answer
- Misstating time complexity as O(E log V) instead of O(V * E)
Best Answer (HR Friendly)
“Bellman-Ford is a shortest-path algorithm that repeatedly relaxes every edge to gradually improve distance estimates until they are correct, and it is the algorithm I reach for when a graph might contain negative weights, since Dijkstra cannot handle those safely. It is slower than Dijkstra but has the extra ability to detect if a negative cycle makes 'shortest path' meaningless.”
Code Example
def bellman_ford(vertices, edges, source):
dist = {v: float("inf") for v in vertices}
dist[source] = 0
for _ in range(len(vertices) - 1):
for u, v, weight in edges:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
for u, v, weight in edges:
if dist[u] + weight < dist[v]:
raise ValueError("Graph contains a negative-weight cycle")
return distFollow-up Questions
- How would you reconstruct the actual shortest path, not just the distance?
- Why does Dijkstra fail on graphs with negative edge weights?
- How would you find which vertices are affected by a detected negative cycle?
- How does SPFA improve on the naive Bellman-Ford relaxation order in practice?
MCQ Practice
1. What is the time complexity of the Bellman-Ford algorithm on a graph with V vertices and E edges?
Bellman-Ford performs V-1 passes over all E edges, giving O(V * E) time.
2. Why does Bellman-Ford perform exactly V-1 relaxation passes?
A simple shortest path visits each vertex at most once, so it has at most V-1 edges, which bounds the passes needed.
3. What does it mean if an edge can still be relaxed after V-1 passes?
A further improvement after V-1 passes proves a negative-weight cycle exists on some path from the source.
Flash Cards
What problem does Bellman-Ford solve? — Single-source shortest paths in a weighted graph, including graphs with negative edge weights.
What is Bellman-Ford's time complexity? — O(V * E), from V-1 passes over all E edges.
How does Bellman-Ford detect a negative cycle? — By running one extra relaxation pass — if any distance still improves, a negative cycle exists.
How does Bellman-Ford differ from Dijkstra on negative weights? — Bellman-Ford handles them correctly; Dijkstra's greedy choice can produce wrong results with negative edges.