DSA Tracker

Visualize

Bellman-Ford Algorithm

Relax every edge, n - 1 times, even the negative ones

time O(V * E)space O(V)

A negative edge weight breaks Dijkstra's core assumption — that settling the cheapest unvisited vertex is safe forever — because a later negative edge can still undercut an already-settled distance. Bellman-Ford gives up the greedy shortcut and instead relaxes every edge, unconditionally, n - 1 times: any simple shortest path has at most n - 1 edges, so n - 1 full passes are guaranteed to propagate the true distance that far, however many hops it takes. A final nth pass that still finds an improvement means a negative cycle is reachable and no shortest path exists at all. The picture shows every distance as a badge and grows the shortest-path tree as parent pointers change.

Details

Animated on: n = 5, edges = [[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]] (u -> v costing w), source = 0 — shortest distance from 0 to every vertex, with a negative edge in the graph?

Problem:Bellman FordMedium

Relax every edge, n - 1 times, even the negative ones

step 1 / 12

Before any pass

5 vertices, 8 directed edges, and one of them is negative (0->1 costs -1) — that rules out Dijkstra's greedy pick. Every distance starts at ∞ except the source 0, which costs 0. A simple shortest path uses at most 4 edges, so 4 full passes over every edge is enough to find them all.

Pseudocode
1FUNCTION bellmanFord(n, edges, src):
2  FOR v FROM 0 TO n - 1
3    dist[v] <- INFINITY
4  dist[src] <- 0
5  FOR i FROM 1 TO n - 1
6    FOR EACH (u, v, w) IN edges
7      IF dist[u] != INFINITY AND dist[u] + w < dist[v]
8        dist[v] <- dist[u] + w
9  FOR EACH (u, v, w) IN edges
10    IF dist[u] + w < dist[v]
11      REPORT NEGATIVE CYCLE
12  RETURN dist

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. 5 vertices, 8 directed edges, and one of them is negative (0->1 costs -1) — that rules out Dijkstra's greedy pick. Every distance starts at ∞ except the source 0, which costs 0. A simple shortest path uses at most 4 edges, so 4 full passes over every edge is enough to find them all.
  2. Edge 0->1 (weight -1): dist[0] + -1 = 0 + -1 = -1, cheaper than 1's current ∞ — dist[1] <- -1.
  3. Edge 0->2 (weight 4): dist[0] + 4 = 0 + 4 = 4, cheaper than 2's current ∞ — dist[2] <- 4.
  4. Edge 1->2 (weight 3): dist[1] + 3 = -1 + 3 = 2, cheaper than 2's current 4 — dist[2] <- 2.
  5. Edge 1->3 (weight 2): dist[1] + 2 = -1 + 2 = 1, cheaper than 3's current ∞ — dist[3] <- 1.
  6. Edge 1->4 (weight 2): dist[1] + 2 = -1 + 2 = 1, cheaper than 4's current ∞ — dist[4] <- 1.
  7. Edge 3->2 (weight 5): dist[3] + 5 = 6, not cheaper than 2's current 2 — no change.
  8. Edge 3->1 (weight 1): dist[3] + 1 = 2, not cheaper than 1's current -1 — no change.
  9. Edge 4->3 (weight -3): dist[4] + -3 = 1 + -3 = -2, cheaper than 3's current 1 — dist[3] <- -2.
  10. Passes 2 through 4 run over every edge again but change nothing — every distance already reached its final value in pass 1. The algorithm cannot know that in advance, so it still pays for all 4 passes in the worst case.
  11. One extra pass over every edge relaxes nothing further, which proves no negative cycle is reachable from 0 — the distances above are final and safe to report.
  12. RETURN [0, -1, 2, -2, 1]. The highlighted arrows are the shortest-path tree — follow one backwards from any vertex to read off its cheapest route from 0.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Bellman Ford in the editorAll Graph problemsBack to roadmap