the Bellman-Ford algorithm
/ BEL-mun FORD /
Dijkstra is clever and fast but fragile: it breaks when roads can have negative cost. Bellman-Ford trades that cleverness for brute patience. It does not try to be smart about the order it processes things — it simply relaxes every single edge, over and over, enough times that the true distances cannot help but emerge. Slower, but it survives negative weights, and as a bonus it can tell you when no honest answer exists at all.
The algorithm is short. Set d[source] = 0, everything else infinity. Then repeat V-1 times: relax every edge in the graph once. Why exactly V-1 passes? Any shortest path has at most V-1 edges (more would repeat a vertex, and with no negative cycle a repeat never helps). After pass number k, every shortest path that uses at most k edges has been fully relaxed and is correct — this is the loop invariant, proved by induction on k: pass 1 gets all one-edge shortest paths right, and each later pass extends correct paths by one more edge. So after V-1 passes, every shortest path is found. The running time is O(V * E), since each of V-1 passes touches all E edges.
Bellman-Ford is the go-to whenever negative edge weights appear — currency-arbitrage graphs, some scheduling problems, and as the first phase of Johnson's all-pairs algorithm. Its other gift is detection: run one extra (V-th) relaxation pass; if any edge can still be relaxed, a negative cycle is reachable and the shortest-path problem has no finite answer. The honest cost is speed — O(V*E) is much worse than Dijkstra's near-linear time, so use Bellman-Ford only when you actually need negative weights or cycle detection.
Vertices s, a, b, edges s->a (4), a->b (-2), s->b (5). Pass 1 (relax in this order): d[a]=4, then d[b]=min(5, 4-2)=2. After V-1 = 2 passes nothing improves, so dist(a)=4, dist(b)=2. A negative edge is handled correctly, which Dijkstra could not guarantee.
V-1 full passes suffice because a shortest path has at most V-1 edges; each pass extends correct paths by one edge.
The order edges are relaxed within a pass affects how fast estimates drop but not correctness after all V-1 passes; the V-1 bound is a worst case, and many graphs converge sooner (you may stop early once a pass changes nothing).