Module A-7 — Shortest Paths II: Bellman-Ford and Floyd-Warshall
What this module covers: Module A-6 flagged Dijkstra's one hard requirement: non-negative edge weights. This module covers the algorithm that handles negative weights correctly — Bellman-Ford — plus how to detect a negative cycle (a path that can be made arbitrarily cheap by looping forever), and Floyd-Warshall, which computes shortest paths between every pair of nodes at once, built directly on Module P-13/P-14's dynamic programming patterns.
Bellman-Ford: Relax Every Edge, Repeatedly
Where Dijkstra greedily commits to one node at a time (and breaks on negative weights because of that commitment), Bellman-Ford takes a much more repetitive, less clever approach that happens to be exactly what makes it correct even with negative edges: relax every single edge, V − 1 times, where "relax" means "check if going through this edge would improve the known distance to its destination, and update if so."
typescript
Why exactly V − 1 passes: the shortest path between any two nodes, if one exists, uses at most V − 1 edges (a path can't usefully visit more than every node once — visiting a node twice would mean it contains a cycle, which is never necessary in a shortest path unless that cycle is negative). Each full pass over every edge can extend the "settled" shortest-path knowledge by one additional edge of depth, so after V − 1 passes, every shortest path — however many edges it needs, up to that maximum — has had enough opportunity to fully propagate through relaxation. This repetitive brute-force approach, unlike Dijkstra's greedy commitment, never permanently rules out revisiting a node's distance, which is exactly why negative edges don't break it: nothing is ever assumed "final" until all V − 1 passes complete.
Detecting Negative Cycles
If a graph contains a cycle whose total weight is negative, "shortest path" stops being well-defined for any node reachable from that cycle — you could keep looping around it, making the total cost lower and lower forever, with no actual minimum. Bellman-Ford detects this directly: after V − 1 relaxation passes should have already found every genuine shortest path, one more pass that still finds an improvement means the graph must contain a negative cycle — because there's no other way a legitimate shortest path could take more than V − 1 edges to settle. This is a real, practical capability Dijkstra has no equivalent for at all: Dijkstra's greedy strategy doesn't just fail silently in the presence of negative cycles — it has no built-in way to notice the problem exists in the first place.
Floyd-Warshall: Every Pair, at Once
Sometimes the actual question isn't "shortest path from one specific start" but "shortest path between every pair of nodes." Running Bellman-Ford (or Dijkstra) from every single node individually would work, but Floyd-Warshall computes all pairs directly, using a dynamic programming recurrence in the exact spirit of Modules P-13 and P-14:
typescript
The state here — this module's version of "what does dp[...] represent" from Module P-13 — is: after considering intermediate nodes 1 through k, what's the shortest known path from i to j? At each step, for every pair (i, j), the algorithm asks a single question: is routing through node k cheaper than the best path already known that doesn't use k? Three nested loops over all vertices gives O(V³) — noticeably more expensive per-run than a single Bellman-Ford or Dijkstra call, but it computes shortest paths for every pair simultaneously, which would otherwise require running a single-source algorithm once per node.
Where This Shows Up in Your Stack
Currency arbitrage detection: model currencies as nodes and exchange rates as edge weights using -log(rate) (a standard trick that turns "maximize product of exchange rates" into "minimize sum of weights") — a negative cycle in this graph corresponds directly to a genuine arbitrage opportunity, a sequence of trades that profits from nothing but the exchange rates themselves. Bellman-Ford's negative-cycle detection is the literal mechanism some real trading-adjacent tools use to search for this.
Distance-vector routing protocols (RIP, and historically similar protocols) work by having each router repeatedly share its known distances with neighbors and relax based on what it hears — structurally the same repeated-relaxation idea as Bellman-Ford, run in a distributed fashion across routers rather than centrally over an explicit edge list.
All-pairs shortest path for small, dense graphs — precomputing a full distance table between every pair of locations on a small map (a game level, a warehouse floor plan, a fixed set of service regions) so that any future "shortest path between X and Y" query is an O(1) table lookup rather than a fresh graph search — is exactly Floyd-Warshall's use case, trading a more expensive one-time O(V³) computation for instant lookups afterward.
Summary
Bellman-Ford relaxes every edge V − 1 times, correctly handling negative edge weights precisely because it never commits permanently to a node's distance the way Dijkstra's greedy strategy does.
A negative cycle is detected by checking for further improvement on a V-th pass — a capability Dijkstra has no equivalent for, since its greedy approach can't even recognize the problem exists.
Floyd-Warshall computes shortest paths between every pair of nodes at once, using a DP recurrence (Modules P-13/P-14's shape) that asks, for each intermediate node k, whether routing through k improves any pair's currently known shortest path.
Floyd-Warshall's O(V³) cost is worth it specifically when "every pair" is genuinely needed, or when a graph is small/dense enough that precomputing a full distance table pays off against many future queries.
Real applications of both: currency arbitrage detection via negative-cycle checking, distance-vector routing protocols' distributed relaxation, and precomputed all-pairs distance tables for small, fixed maps.
The next module, Topological Sort: Kahn's Algorithm and DFS-Based Ordering, moves from shortest-path costs back to pure ordering — determining a valid sequence for tasks with dependencies, and detecting when no valid sequence exists at all.
Knowledge Check
Why does Bellman-Ford relax every edge specifically V − 1 times, rather than some other fixed number of passes?
Why does Dijkstra's algorithm (Module A-6) have no way to detect a negative cycle, while Bellman-Ford does?
In floydWarshall, what does the check throughK < dist.get(i)!.get(j)! specifically determine, and how does this relate to the dynamic programming approach used in Modules P-13/P-14?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionbellmanFord( edges:[string,string,number][],// [from, to, weight][] vertices:string[], start:string): Map<string,number>|null{const distances =newMap<string,number>();for(const v of vertices) distances.set(v,Infinity); distances.set(start,0);// Relax every edge, V - 1 times — enough for a shortest path to "propagate" across the whole graphfor(let i =0; i < vertices.length -1; i++){for(const[from, to, weight]of edges){const distFrom = distances.get(from)!;if(distFrom !==Infinity&& distFrom + weight < distances.get(to)!){ distances.set(to, distFrom + weight);// found a cheaper way to reach `to`}}}// One more pass: if any distance can still improve, a negative cycle existsfor(const[from, to, weight]of edges){const distFrom = distances.get(from)!;if(distFrom !==Infinity&& distFrom + weight < distances.get(to)!){returnnull;// negative cycle detected — shortest path is not well-defined}}return distances;}
functionfloydWarshall(vertices:string[], edges:[string,string,number][]): Map<string, Map<string,number>>{const dist =newMap<string, Map<string,number>>();for(const u of vertices){ dist.set(u,newMap());for(const v of vertices){ dist.get(u)!.set(v, u === v ?0:Infinity);}}for(const[from, to, weight]of edges){ dist.get(from)!.set(to, weight);}// Try every node k as a possible "intermediate stop" between every pair (i, j)for(const k of vertices){for(const i of vertices){for(const j of vertices){const throughK = dist.get(i)!.get(k)!+ dist.get(k)!.get(j)!;if(throughK < dist.get(i)!.get(j)!){ dist.get(i)!.set(j, throughK);// routing through k is cheaper than the current known path}}}}return dist;}