Bellman-Ford Algorithm, step by step.

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

What is the Bellman-Ford algorithm?

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.

How does Bellman-Ford work? Relaxing every edge in passes

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.

Bellman-Ford pseudocode with early termination

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.

Bellman-Ford example: a distance table step by step

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.

Bellman-Ford on a directed graph with a negative edge

All steps as text
  1. Find the shortest paths from A to all vertices in the directed graph using Bellman-Ford algorithm.
  2. Use the table to track distances from A to every vertex. Unknown distances are marked as ∞.
  3. Begin pass 1 of 5 — check all edges one by one, updating distances where a shorter path is found. The algorithm performs at most V−1 relaxation passes, where V is the number of vertices.
  4. Consider the edge from A to B.
  5. Set B's distance to 5 and record A as its predecessor.
  6. Consider the edge from B to C.
  7. With distance to B known from table, set C's distance to 10 (AB + BC = 5 + 5) and update the table.
  8. Consider the edge from A to D.
  9. Set D's distance to 2 and record A as its predecessor.
  10. Consider the edge from D to E.
  11. With distance to D known from table, set E's distance to 7 (AD + DE = 2 + 5) and update the table.
  12. Consider the edge from C to F.
  13. With distance to C known from table, set F's distance to 20 (AC + CF = 10 + 10) and update the table.
  14. Consider the edge from E to F.
  15. With distance to E known from table, a shorter path to F found (AE + EF = 7 + 7): update distance from 20 to 14 and set E as its predecessor.
  16. Consider the edge from E to B.
  17. With distance to E known from table, a shorter path to B found (AE + EB = 7 + (-10)): update distance from 5 to -3 and set E as its predecessor.
  18. Pass 1 complete. All edges have been checked.
  19. Relaxation occurred in the previous pass — continue with pass 2 of 5.
  20. Consider the edge from A to B.
  21. Since distance to B known from table is -3, the path via A (weight of edge AB is 5) is not shorter — make no update.
  22. Consider the edge from B to C.
  23. With distance to B known from table, a shorter path to C found (AB + BC = -3 + 5): update distance from 10 to 2 and set B as its predecessor.
  24. Consider the edge from A to D.
  25. Since distance to D via A equals the current value (2) — make no update.
  26. Consider the edge from D to E.
  27. Since distance to E via D equals the current value (AD + DE = 2 + 5) — make no update.
  28. Consider the edge from C to F.
  29. With distance to C known from table, a shorter path to F found (AC + CF = 2 + 10): update distance from 14 to 12 and set C as its predecessor.
  30. Consider the edge from E to F.
  31. Since distance to F known from table is 12, the path via E (AE + EF = 7 + 7) is not shorter — make no update.
  32. Consider the edge from E to B.
  33. Since distance to B via E equals the current value (AE + EB = 7 + (-10)) — make no update.
  34. Pass 2 complete. All edges have been checked.
  35. Relaxation occurred in the previous pass — continue with pass 3 of 5.
  36. Consider the edge from A to B.
  37. Since distance to B known from table is -3, the path via A (weight of edge AB is 5) is not shorter — make no update.
  38. Consider the edge from B to C.
  39. Since distance to C via B equals the current value (AB + BC = -3 + 5) — make no update.
  40. Consider the edge from A to D.
  41. Since distance to D via A equals the current value (2) — make no update.
  42. Consider the edge from D to E.
  43. Since distance to E via D equals the current value (AD + DE = 2 + 5) — make no update.
  44. Consider the edge from C to F.
  45. Since distance to F via C equals the current value (AC + CF = 2 + 10) — make no update.
  46. Consider the edge from E to F.
  47. Since distance to F known from table is 12, the path via E (AE + EF = 7 + 7) is not shorter — make no update.
  48. Consider the edge from E to B.
  49. Since distance to B via E equals the current value (AE + EB = 7 + (-10)) — make no update.
  50. Pass 3 complete. No relaxations occurred — remaining passes are skipped and the shortest paths are finalized.
  51. Use the table to build the shortest path from A to F as an example — the table provides the shortest path from A to any vertex in the graph.
  52. Vertex C is identified as the predecessor of F.
  53. Vertex B is identified as the predecessor of C.
  54. Vertex E is identified as the predecessor of B.
  55. Vertex D is identified as the predecessor of E.
  56. The shortest path from A to F is completely defined.
  57. Draw the shortest path between these vertices to visualize the result.
  58. The shortest path from A to F has been successfully drawn.
  59. The shortest path from A to F, A → D → E → B → C → F, weighs 2 + 5 + (-10) + 5 + 10 = 12. The table gives the distances from A: B -3, C 2, D 2, E 7 and F 12.
Bellman-Ford on a directed graph with a negative edge. Last step: The shortest path from A to F, A → D → E → B → C → F, weighs 2 + 5 + (-10) + 5 + 10 = 12. The table gives the distances from A: B -3, C 2, D 2, E 7 and F 12.

How does Bellman-Ford detect a negative cycle?

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.

Why V − 1 passes, and why fewer are often enough

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.

Negative cycle detection: the extra pass

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.

Bellman-Ford time and space complexity

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.

Bellman-Ford vs Dijkstra, SPFA and Floyd-Warshall

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.

Bellman-Ford in Python, Java and C++

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.

Applications of Bellman-Ford

  • Distance-vector routing: in RIP (RFC 1058) a router's distance to a destination is the least, over its neighbors, of the link cost plus that neighbor's distance.
  • Currency arbitrage: weight each exchange rate r as −log r, and a profitable round of trades becomes a negative cycle.
  • Johnson's algorithm: Bellman-Ford from an added vertex gives each vertex a value h that makes every weight w + h(u) − h(v) non-negative, so Dijkstra can then run from every vertex.
  • Interview problems: LeetCode 787, Cheapest Flights Within K Stops, makes K + 1 passes, each over a copy of the previous distances, so that pass i allows at most i edges.

One graph here.
Negative cycles 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 negative cycles, drawn

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.

Your graph, negative weights allowed

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.

How it works, where it stops

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.

Python, Java and C++

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.

Quiz

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.

Other graph topics

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.

Every edge,
every pass.

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