Graph algorithms / interactive lesson
Compute shortest paths in directed graphs with negative edge weights. Watch repeated relaxation rounds propagate cheaper routes and use one extra sweep to detect reachable negative cycles.
Relaxation timeline
Set A as the source
About the algorithm
Bellman-Ford computes shortest paths from one source in a directed weighted graph, even when edges may have negative weights. It repeatedly relaxes every edge. A final extra sweep detects whether a reachable negative cycle makes shortest distances undefined.
The algorithm is associated with Richard Bellman and Lester Ford Jr., who described related relaxation methods in the late 1950s. Edward F. Moore also developed a closely related approach. Bellman-Ford became a foundation for distance-vector routing protocols.
Initialize the source distance to 0 and all others to infinity. Sweep every directed edge V - 1 times. For edge u -> v, test whether distance[u] + weight(u,v) improves distance[v]. Each successful relaxation propagates a shorter route.
After the normal rounds, sweep the edges once more. If any reachable distance still improves, the graph contains a reachable negative cycle. Repeating that cycle would lower the route cost without bound, so no finite shortest path exists.
Bellman-Ford is useful for graphs with rebates, gains, penalties, or other negative costs. It also appears in distributed routing, arbitrage detection, and constraint systems. For graphs with only non-negative weights, Dijkstra is usually faster.
Code companion
Connect each visual decision to an implementation pattern.
distance[source] = 0
distance[other nodes] = infinity
repeat V - 1 times:
changed = false
for each directed edge (u, v, weight):
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
predecessor[v] = u
changed = true
if not changed:
break
for each directed edge (u, v, weight):
if distance[u] + weight < distance[v]:
report reachable negative cycle
return distance, predecessor