The Bellman-Ford algorithm finds the shortest paths from one source vertex to every other vertex of a weighted directed graph, even with negative weights, and reports a negative cycle if the source can reach one. It relaxes every edge in up to V − 1 passes, in O(V·E) time. This page explains how it works, with a step-by-step animation from the VisiGrab app: Bellman-Ford and its distance table on a graph with a negative edge.
// how the bellman-ford algorithm works
The Bellman-Ford algorithm finds the shortest paths from one source vertex to every other vertex of a weighted directed graph, even when some weights are negative. One run gives each vertex the source can reach a distance, the weight of its shortest path, and a predecessor, the vertex just before it on that path. If the source can reach a negative cycle, a loop whose weights add up to less than 0, it reports that one exists instead.
It is named after Lester Ford Jr. (1956) and Richard Bellman (1958). Alfonso Shimbel described it first, in 1955, and Edward F. Moore published a variant in 1959, so it is also called Bellman-Ford-Moore. On an undirected graph each edge counts as two directed edges, which works only while no weight is negative.
Bellman-Ford needs only an edge list. Unlike Dijkstra's algorithm, it has no priority queue and fixes no distance before the run ends, so a negative edge met late still counts. The app sweeps the list in the same order on every pass. Any order gives the same distances, but the order decides how many passes are needed.
1. Initialize: the source gets distance 0 and every other vertex ∞, meaning not reached yet. No vertex has a predecessor.
2. Relax every edge: for each edge u → v, if u's distance plus the edge's weight is less than v's distance, store the sum as v's distance and u as v's predecessor. This is relaxing the edge. Edges leaving a vertex still at ∞ are skipped.
3. Repeat in passes: one sweep over all the edges is a pass. With V vertices, make at most V − 1 passes. Each edge sees the latest distances, even those written earlier in the same pass. If a pass changes nothing, stop early: the distances are final.
4. Check for a negative cycle: if pass V − 1 still changed a distance, sweep once more; a run that stopped early needs no check. An edge that still relaxes proves a negative cycle.
5. Read the path back: from the target, step from predecessor to predecessor until the source, then reverse the vertices met.
In pseudocode, with the names of the app's full source on GitHub, where u, v and w are an edge's source, destination and weight:
for each vertex v
distances[v] = infinity
predecessors[v] = none
distances[source] = 0
updated = false
repeat V - 1 times
updated = false
for each edge (u, v, w)
if distances[u] == infinity
continue
new_dist = distances[u] + w
if new_dist < distances[v]
distances[v] = new_dist
predecessors[v] = u
updated = true
if not updated
break
if updated
for each edge (u, v, w)
if distances[u] == infinity
continue
new_dist = distances[u] + w
if new_dist < distances[v]
return "negative cycle"
return distances, predecessors
updated records whether a pass relaxed an edge; if it stays false, break ends the loop early. continue skips edges out of a vertex at infinity: where ∞ is stored as a large number, ∞ plus a negative weight would otherwise look shorter. The test new_dist < distances[v] is the relaxation, so on a tie the old predecessor stays. The second loop is the extra pass: it runs only if the last pass left updated true, and returns at the first edge that still relaxes.
The player below runs Bellman-Ford from A on the app's default graph with its distance table and a pass counter. Pass 3 changes nothing, so the run stops early and reads the path A → D → E → B → C → F, of weight 12, back from the table. In the sums and under the table, a pair such as AE stands for E's distance from A, not an edge: the graph has no edge A → E.
After pass V − 1, if that pass still changed a distance, it sweeps every edge once more. Without a negative cycle every distance is final by then, so an edge that still lowers a distance proves that the source can reach a negative cycle. A pass that changes nothing rules one out: in the player, pass 3 changes nothing, so the run stops early and skips the extra pass.
Without a negative cycle, a shortest path repeats no vertex, so it has at most V − 1 edges. After pass k, every vertex whose shortest path has at most k edges holds its final distance, whatever the edge order.
In the player, F's shortest path has five edges, yet only passes 1 and 2 change anything. A → D, D → E and E → B come in that order in the list, so pass 1 carries −3 to B, three edges deep; only B → C and C → F, listed before E → B, need pass 2.
Bellman-Ford is dynamic programming, not a greedy method: the best route to v with at most k edges is either the best one with at most k − 1 edges or, for some edge u → v, the best such route to u plus that edge, whichever is shorter.
A route can loop round a negative cycle for ever, each lap for less, so vertices reachable through it have no shortest distance. Without such a cycle nothing changes after pass V − 1, so an edge that relaxes in one more pass proves a cycle.
To find the cycle's vertices, step back V times through the predecessors from the vertex the extra pass lowered: this lands on the cycle, not on a path into it. Then keep stepping back until a vertex repeats.
Only cycles the source can reach are found, since edges leaving a vertex at ∞ never relax. To catch any negative cycle, start every distance at 0, as if a new source had an edge of weight 0 to each vertex.
Each pass checks all E edges, and there are at most V − 1 passes plus the extra one: O(V·E) time, or O(V3) on a complete graph, where E is close to V2. With early termination, the best case is O(E): one pass sets the distances and a second confirms them. Extra space is O(V) for the distances and predecessors, besides the O(E) edge list.
With no negative weight, Dijkstra's algorithm finds the same distances faster. With one, Dijkstra can fail: on the player's graph it settles B at 5 before E → B can lower it, and gives F 14 by A → D → E → F instead of 12.
On a graph without cycles, such as the player's, relaxing each vertex's edges once, in topological order (A, D, E, B, C, F), gives the same distances in O(V + E). SPFA tries again only the edges of vertices whose distance just changed: usually faster, with the same O(V·E) worst case. Floyd-Warshall finds the paths between all pairs in O(V3), negative weights included.
The app's listing is the same function in all three languages: the pseudocode above without predecessors. The full source on GitHub, in Python, Java and C++, also returns the predecessors and a negative-cycle flag, and rebuilds a path from them.
// in the app
In VisiGrab, Bellman-Ford runs on four example graphs with its distance table, a pass counter and a message for every edge it checks.
Two of the four examples hold a negative cycle. All five passes still change a distance, an edge relaxes in the extra pass, and the app draws the cycle: B → C → F → E → B, weight −6, in one and B → E → F → D → B, weight −8, in the other.
Switch the Graph Constructor to Bellman-Ford and draw a directed graph of up to 12 vertices with weights from −99 to 99. After Apply, pick a start and an end vertex: each Next draws the shortest path one vertex further, and the app says when there is no path or names the vertices of a negative cycle.
The info dialog defines relaxation, shows a shortest path on a small graph with a negative edge, explains the early exit, sets O(V·E) against Dijkstra's O((V + E) log V) and covers negative cycles. It names network routing and currency arbitrage as uses.
The listing fills the distances, leaves the loop after a pass with no change, and checks for a negative cycle only if the last pass still changed a distance. Three key points explain each part, and a link opens the full source on GitHub.
Seven questions, with an explanation for every option: relaxation, why V − 1 passes, why negative weights work, a pass with no change, spotting a negative cycle, why it leaves no shortest path, and the cost of sweeping every edge.
Dijkstra's algorithm finds shortest paths faster when no weight is negative, Topological Sort orders a graph without cycles, and Prim and Kruskal build minimum spanning trees.
// build your own
Download VisiGrab to watch the distance table change pass by pass on four example graphs, then draw a graph with negative weights and find its shortest path or its negative cycle.
The Bellman-Ford algorithm is one of 30+ topics. See them all