Bellman-Ford Visualizer

Shortest paths with negative edges, one pass at a time.

  • Pass by pass
  • Negative cycle traced
  • Dijkstra comparison
A small rounded clay table with soft clay knots linked by soft curved links, a small loop of links closing on itself, and a few loose rounded beads.

The guide

Bellman-Ford relaxes every edge again and again, and one extra pass exposes a negative cycle

Why repeated relaxation finds shortest paths when edges can be negative, why |V| - 1 passes are enough, how the final scan catches a cycle, and where the idea lives on in routing.

  • 0, 2, 7, 4, -2 distances from vertex 0 on the example graph
  • 3 of 4 passes used with the early stop, against the worst case
  • -2 weight of the cycle 3, 1, 4 once one edge falls from 7 to 4
  • 0, 6, 7, 4, 2 what Dijkstra's method returns on the example, wrongly
  • 4 and 2 passes for one chain listed far end first, then near end first
Read the full guide Fold the guide 6 min · 10 sources

Most shortest-path lessons start with a greedy idea: always settle the closest unsettled vertex. It is fast, and it is right as long as no edge has a negative weight. The Bellman-Ford method drops the greed and keeps the patience. It looks at every edge, over and over, and lets the distances settle on their own.

Negative edges are not exotic. A refund that reduces a total, a downhill leg on a route, a trade that returns more than it costs: all of them are edges that make a path cheaper as it grows. This is the case the algorithm was built for.

What the algorithm does

Start from a directed graph, which is a set of vertices joined by one-way edges, each carrying a weight. Pick a source. Give the source a distance of zero and every other vertex a distance of infinity, with no predecessor recorded.

Then make a pass. In a pass, visit every edge once, in any order. For an edge from u to v with weight w, ask whether the distance to u plus w is smaller than the distance now recorded for v. If it is, replace the old distance and write u down as the predecessor of v. An edge that starts at a vertex not yet reached is skipped, because infinity plus anything is still infinity.

That step is called relaxation. Every recorded distance is an overestimate of the true one, and each relaxation replaces it with the smaller of the old value and the length of a newly found path. The method is slower than Dijkstra’s, but more versatile, since it accepts negative weights. The algorithm carries the names of Richard Bellman and Lester Ford and was proposed even earlier by Alfonso Shimbel; Edward Moore published a variation in 1959.

Why |V| - 1 passes are enough

Here is the argument, and it fits in a few lines. After the first pass, every vertex reachable from the source by a single edge has a distance no larger than that edge’s weight. After the second pass, every vertex reachable by a path of at most two edges is covered. By induction, after i passes each distance is at most the best path with at most i edges.

A shortest path that has no cycle in it can never use more than |V| - 1 edges, because a path with |V| edges would visit some vertex twice. So |V| - 1 passes cover every cycle-free path, and when no negative cycle exists the best path is cycle-free. The tool checks the statement on its example for i from 1 to 4, and it never finds a violation.

Take the example graph with five vertices numbered 0 to 4 and ten edges, one of them (the edge from 1 to 4) with weight minus 4. Relaxed in the order typed, the distances from vertex 0 come out as 0, 2, 7, 4, -2. The path to vertex 4 runs 0, 2, 3, 1, 4, and the one to vertex 3 runs 0, 2, 3. Two passes change something and a third finds nothing to change, so with the early stop the method uses 3 of the 4 passes that the worst case allows.

The order of the edges matters, but not the answer

The final distances do not depend on the order of the edges. The pass count does. List a four-edge chain from its far end and each pass moves the news only one step: the method needs all 4 passes. List the same chain from its near end and a single pass carries the news the whole way, so the work takes 2 passes, one that changes things and one that confirms.

This is the reason the early stop is worth having. A pass that improves nothing proves that no later pass will, so the method can stop. The cost drops from the number of vertices times the number of edges to the number of edges times the length of the longest shortest path. The worst case is unchanged.

Cut the loop short and the answer is wrong in a plain way. Stop the far-end chain at |V| - 2 passes and the distances read 0, 1, 2, 3, and infinity: the last vertex has not been reached. The page lets you watch that happen, one pass at a time, and reverse the order of the edges with a single switch.

One more pass finds a negative cycle

Now change the edge from 4 to 3 so that its weight falls from 7 to 4. A cycle appears: 3 to 1 to 4 and back to 3, with weights of minus 2, minus 4 and 4. It weighs minus 2. Each trip around it makes any path through it cheaper, so for every vertex the cycle can reach there is no cheapest path at all.

The algorithm gets the news from one extra scan. If no cycle exists, the |V| - 1 passes leave every edge satisfying the inequality that distance to v is at most distance to u plus w. Add those inequalities around a cycle and the distances cancel, which would force the cycle’s weight to be zero or more. So if the final scan still finds an edge that improves a distance, a negative cycle is reachable from the source.

Skip that scan and the damage is quiet. On the changed graph the method returns the distances -2, 0, 7, 0, and -4, and no warning appears, though none of them is final. Run the scan and the page marks the cycle with dashes.

There is a subtle point about reporting it. The edge found by the scan is reachable from the cycle but need not lie on it. To find the cycle, set the predecessor of the edge’s head, walk back along predecessors until a vertex repeats, and then follow predecessors from that vertex until you return to it. A directed cycle is a closed trail in which only the first and last vertices are equal, so the walk stops at the repeat. Listed in forward order, the cycle reads 3, 1, 4.

Dijkstra, Floyd-Warshall and Johnson

Dijkstra’s method settles a vertex when it is the closest unsettled one and never looks back. With a negative edge that is a mistake, because a later route may be cheaper. On the example it returns 0, 6, 7, 4, 2, and so it gets vertices 1 and 4 wrong: the right values are 2 and -2. A small counterexample on its Wikipedia page shows the same failure with three vertices.

Floyd-Warshall gives the shortest paths between all pairs and also accepts negative weights without negative cycles; this page uses it to check its own work. Johnson’s algorithm runs Bellman-Ford once to reweight the edges so that none is negative, then lets Dijkstra take over, and it stops if the first stage finds a negative cycle.

Where it lives on

Distance-vector routing is Bellman-Ford spread across a network. Each router knows only its own links. It advertises its distances to its neighbours, hears theirs, and updates its table, and the tables converge as a pass of relaxation converges. The Routing Information Protocol is a well-known case, and it counts hops, with 16 hops meaning unreachable.

The old weakness is also visible there. A router cannot tell whether a neighbour’s advertised route runs through itself, so bad news travels slowly and distances can climb one step at a time, the count to infinity. The protocol caps the hop count to limit that damage. A routing loop in a network is the cousin of a negative cycle: a closed path that keeps looking worth taking.

What this page does not cover

The page runs the plain version that relaxes every edge in every pass. The queue-based variant is only named, and all-pairs methods, potentials, huge graphs and real routing protocols are outside it. Within its caps it takes up to 40 vertices and 200 edges. The comparison with Dijkstra and the self-test run in a background worker, so a large graph cannot freeze the page, and nothing you type leaves your device.

Sources

Every source consulted for this guide. Links checked November 12, 2026.

  1. Bellman-Ford algorithm Wikipedia (CC BY-SA)
  2. Dijkstra's algorithm Wikipedia (CC BY-SA)
  3. Shortest path problem Wikipedia (CC BY-SA)
  4. Directed graph Wikipedia (CC BY-SA)
  5. Cycle (graph theory) Wikipedia (CC BY-SA)
  6. Distance-vector routing protocol Wikipedia (CC BY-SA)
  7. Routing Information Protocol Wikipedia (CC BY-SA)
  8. Floyd-Warshall algorithm Wikipedia (CC BY-SA)
  9. Johnson's algorithm Wikipedia (CC BY-SA)
  10. Web Workers API MDN Web Docs (CC BY-SA)