Bellman–Ford algorithm: shortest paths with negative edges
Follow two edge scans to find a cheaper route, then see why a reachable negative cycle prevents some shortest distances from existing.
Bellman–Ford finds shortest routes from one start even when an edge has a negative weight. It repeatedly improves the known distances. A reachable negative cycle makes distances to that cycle and places beyond it unbounded below; the algorithm can detect this.
Going directly from S to A costs 4. Going from S to B costs 5, but the edge from B to A costs −3. The second route costs 2. Bellman–Ford keeps checking routes, so it can replace the first answer with the cheaper one.
The indirect route in the example is more expensive at first: reaching B costs 5, while reaching A directly costs 4. Only the final edge makes the indirect route cheaper. A shortest-path algorithm that treats A’s distance as finished too early can miss that change. Bellman–Ford allows an earlier answer to improve.
Improve one distance at a time#
An edge is a directed connection with a cost. For S → A: 4, the cost of that connection is 4. In this illustrative graph, the other edges are S → B: 5 and B → A: -3.
Start with distance 0 to S. Mark A and B as infinity, meaning no route has been found yet. For each edge, add its cost to the best known distance at its starting vertex. If that gives a cheaper route to its destination, replace the destination’s distance. This update is called relaxation.
Scan the edges in the order B → A, S → A, S → B:
| Point in the calculation | Distance to S | Distance to A | Distance to B |
|---|---|---|---|
| Before scanning | 0 | infinity | infinity |
| After the first complete scan | 0 | 4 | 5 |
| After the second complete scan | 0 | 2 | 5 |
During the first scan, B → A cannot help because B is still unreachable. During the second, it improves A to 5 - 3 = 2. Scanning in another order could discover the same improvement sooner. Correctness must not depend on getting that fortunate order.
Why the number of scans is limited#
Let V be the number of vertices. A path that does not repeat a vertex contains at most V−1 edges. When no reachable negative cycle interferes, repeating a vertex is not necessary to obtain a cheapest route. After k complete scans, routes using at most k edges have had enough opportunities to update their destinations. At most V−1 scans therefore suffice.
This Python function accepts a list of distinct vertex names and a reusable list of directed edges (start, end, integer_weight). It reports unreachable vertices as infinity. It returns distances, not a sequence of vertices to follow.
def bellman_ford(vertices, edges, source):
distance = {v: float("inf") for v in vertices}
if source not in distance:
raise ValueError("source must be a listed vertex")
if any(u not in distance or v not in distance for u, v, _ in edges):
raise ValueError("every edge endpoint must be a listed vertex")
distance[source] = 0
for _ in range(len(vertices) - 1):
changed = False
for u, v, weight in edges:
if distance[u] != float("inf") and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
changed = True
if not changed:
break
for u, v, weight in edges:
if distance[u] != float("inf") and distance[u] + weight < distance[v]:
raise ValueError("negative cycle reachable from source")
return distanceA scan with no improvements allows an early stop: repeating the same comparisons cannot change the same distances. With E edges, the repeated scans cost O(VE) time, in addition to initialising the V distance entries. The distance map uses O(V) space; the supplied edge list is separate. The Big-O guide explains why these counts describe how work grows rather than a runtime in seconds.
When a cheapest route does not exist#
Change the graph so that A → B costs 1 and B → A costs −3. Each trip around that reachable loop lowers the total by 2. Going around again always produces a cheaper walk, so there is no finite minimum for A, B or any vertex reachable from them.
That is what the extra scan checks. An improvement after V−1 scans reveals a reachable negative cycle. The check against infinity prevents an unrelated cycle in a disconnected part of the graph from being reported as reachable from S. The function raises an error for the whole request; it does not separately return the distances that remain well-defined.
For graphs with nonnegative weights, Dijkstra’s algorithm can avoid repeated full edge scans. Kruskal’s algorithm also accepts negative weights, but it minimises the cost of connecting vertices with a tree, not the cost of routes from a start. Decide which question you need answered before choosing between them.
Questions people also ask
2 QUESTIONSDoes a negative cycle anywhere in the graph cause failure?
No. The cycle must be reachable from the chosen start. It makes distances unbounded below only for vertices on the cycle or reachable from it. The simple function on this page raises an error for any reachable negative cycle instead of returning unaffected distances.
Does this function return the actual routes?
No. It returns distances. To recover routes, record a predecessor whenever a distance improves, then trace those predecessors after checking for reachable negative cycles.