Pattern visualizer

Bellman-Ford Algorithm

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. 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?.

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

time O(V * E)space O(V)step 1 / 12

Before any pass

∞

line 4

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap