The Bellman–Ford algorithm finds shortest paths from a single source node to every
other node in a weighted directed graph — even when some edges have
negative weights, which Dijkstra's algorithm cannot handle correctly.
It works by repeatedly relaxing every edge: if going through an edge
gives a shorter path to its destination than what's currently known, the distance is
updated. After at most V − 1 passes over all edges (where V is the number
of vertices), the shortest distances are guaranteed to be found — provided the graph
has no negative-weight cycle reachable from the source.
∞ except the source, which starts at 0 (shown in gold).dist[u] + w(u,v) < dist[v].Because it only needs edge lists (no priority queue) and tolerates negative weights, Bellman–Ford is the algorithm behind distance-vector routing protocols like RIP, where each router repeatedly "relaxes" its known distances by gossiping with neighbours.
A 3D directed weighted graph — including negative-weight edges — where each edge relaxation step animates live, building a shortest-path tree from a golden source node, with a toggle to introduce a negative cycle and watch the algorithm detect it on the extra verification pass.
Bellman–Ford relaxes every edge in the graph up to V−1 times, updating each node's shortest known distance from the source. A final Vth pass checks whether any edge can still relax — if so, a negative-weight cycle exists and no finite shortest path is defined.
Pick a preset graph, or flip on "Introduce negative cycle" to add a back-edge that creates one. Press Play to auto-run edge relaxations, or Step through them one at a time. Teal edges show the current shortest-path tree; red edges carry negative weight.
Distance-vector routing protocols like RIP are essentially distributed, gossip-based versions of Bellman–Ford — each router relaxes its known distances using updates from its neighbours, round after round.