--- title: All-Pairs and Negative Weights module: Graphs moduleNumber: 6 lessonNumber: 7 order: 607 summary: | Dijkstra's greedy schedule breaks the moment an edge goes negative. We give it up for dynamic programming: Bellman-Ford derived as a DP over edge budgets, with its negative-cycle detector, and Floyd-Warshall computing the distance between _every_ pair of vertices via a DP over which vertices a path may pass through. We close with Johnson's algorithm and the arbitrage problems that negative cycles encode. topics: [Shortest Paths, Dynamic Programming] sources: - book: CLRS ref: "Ch. 24 & 25 — Single-Source and All-Pairs Shortest Paths" - book: Erickson ref: "Ch. 9 — Shortest Paths" - book: Skiena ref: "§6 — Weighted Graph Algorithms" practice: - title: 'Cheapest Flights Within K Stops' slug: cheapest-flights-within-k-stops difficulty: Medium - title: 'Find the City With the Smallest Number of Neighbors' slug: find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance difficulty: Medium --- This builds on [Shortest Paths](/algorithms/graphs/shortest-paths), which developed the relaxation primitive and Dijkstra's greedy algorithm for non-negative weights. Dijkstra's whole correctness argument leaned on non-negativity in one place — "extending a path never lowers its cost" — and one negative edge breaks it. Handling negative weights means abandoning the greedy schedule for dynamic programming, which is where we pick up. ## Bellman-Ford as a dynamic program Dijkstra breaks when edges can be **negative** — its greedy finalization assumes a finalized estimate can never improve, which negative edges violate. $\textsc{Bellman-Ford}$ trades speed for generality. It is best derived not as "relax everything repeatedly" but as a genuine [**dynamic program**](/algorithms/dynamic-programming/dp-on-graphs). That framing is worth keeping, because it explains _where the $\abs{V}-1$ comes from_. **The subproblem.** Bound the number of edges a walk may use. For each vertex $v$ and each budget $k$, define $$ \text{OPT}(k, v) = \text{cost of a cheapest } s \rightsquigarrow v \text{ walk using at most } k \text{ edges.} $$ The full answer we want is $\text{OPT}(n-1, v)$ for $n = \abs{V}$, since (as we prove below) shortest paths never need more than $n-1$ edges. **The recurrence.** A cheapest walk to $v$ using at most $k$ edges either uses at most $k-1$ edges already, or it takes one final edge $(u, v)$ after a cheapest $\le (k-1)$-edge walk to $u$. Minimizing over both: $$ \text{OPT}(k, v) = \min\parens{\, \text{OPT}(k-1, v),\; \min_{(u,v)\,\in\,E}\;\text{OPT}(k-1, u) + w(u, v) \,}, $$ with base cases $\text{OPT}(0, s) = 0$ and $\text{OPT}(0, v) = \infty$ for $v \neq s$. This is relaxation in another guise: filling row $k$ of the table from row $k-1$ is one full pass that relaxes every edge. The tabular form makes the layering explicit, with row $k$ holding the best walk of length $\le k$: ```algorithm caption: $\textsc{Bellman-Ford-DP}(G, w, s)$ — the explicit DP table number: 3 $\text{OPT}[0, s] \gets 0$; $\text{OPT}[0, v] \gets \infty$ for $v \neq s$ for $k \gets 1$ to $n - 1$ do // one pass over all edges per row foreach vertex $v \in V$ do $\text{OPT}[k, v] \gets \text{OPT}[k-1, v]$ // inherit: no extra edge foreach edge $(u, v) \in E$ do if $\text{OPT}[k-1, u] + w(u, v) < \text{OPT}[k, v]$ then $\text{OPT}[k, v] \gets \text{OPT}[k-1, u] + w(u, v)$ $v.\pi \gets u$ return $\text{OPT}[n-1, \cdot]$ and $\pi$ ``` **Why stop after $n-1$ rounds?** This is the theorem that licenses the whole algorithm. > **Theorem (Shortest paths are simple).** If $G$ has no negative-cost cycle, then > for all $s, t$ the distance $\delta(s, t)$ is achieved by a path of length > $\le n - 1$. > **Proof.** A short-circuiting argument: any $s \rightsquigarrow t$ **walk** of > length $> n-1$ visits some vertex twice, so it contains a cycle. Excising that > cycle yields a shorter walk of cost no greater than the original (the removed > cycle has non-negative cost). Repeating until no cycle remains leaves a _simple_ > path, with at most $n-1$ edges, that is no more expensive. $\qed$ So the rows of the DP stop changing by row $n-1$. A second, sharper argument gives the same bound, phrased directly in terms of relaxation.[^clrs-relax] It explains not just _that_ $n-1$ rounds suffice but _which_ vertices are already correct after each round. > **Lemma (Path relaxation).** Let $p = \vector{s = v_0, v_1, \dots, v_k}$ be a > shortest path from $s$ to $v_k$. If the edges > $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$ are relaxed **in that order**, > with any other relaxations interleaved arbitrarily between them, then > afterward $v_k.d = \delta(s, v_k)$. > **Proof.** Induction on $i$, with the claim that after the relaxation of > $(v_{i-1}, v_i)$ we have $v_i.d = \delta(s, v_i)$. The base holds before > anything happens: $v_0 = s$ and $s.d = 0 = \delta(s, s)$. For the step, when > $(v_{i-1}, v_i)$ is relaxed we already have > $v_{i-1}.d = \delta(s, v_{i-1})$ by the inductive hypothesis; that value > has not moved since, because no estimate ever drops below its true distance. > The relaxation therefore leaves > $v_i.d \le \delta(s, v_{i-1}) + w(v_{i-1}, v_i) = \delta(s, v_i)$, the equality > by optimal substructure (the prefix of a shortest path is a shortest path). > Since $v_i.d$ can never fall below $\delta(s, v_i)$, it equals it. The > interleaved relaxations are harmless: they only lower estimates, and never > past the truth. $\qed$ Round $i$ of Bellman-Ford relaxes _every_ edge, in particular the $i$-th edge of any shortest path you care to name, and it does so after round $i-1$ handled the $(i-1)$-st. So after round $i$, every vertex whose shortest path uses at most $i$ edges holds its exact distance, and since no shortest path needs more than $n-1$ edges, $n-1$ rounds settle every vertex. The correct region grows along every shortest path by at least one edge per round: $$ % caption: Path relaxation along one shortest path $s \to v_1 \to \dots \to v_4$. Round % $i$ relaxes every edge, in particular edge $i$ of this path; each bracket % marks the prefix whose estimates are guaranteed exact after that round. \begin{tikzpicture}[>=Stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \tikzset{V/.style={circle, draw, minimum size=7mm, font=\small, inner sep=0.5pt}, el/.style={font=\scriptsize, inner sep=1pt}, br/.style={draw=acc}, bl/.style={font=\scriptsize, acc}} \node[V] (v0) at (0,0) {$s$}; \node[V] (v1) at (2.1,0) {$v_1$}; \node[V] (v2) at (4.2,0) {$v_2$}; \node[V] (v3) at (6.3,0) {$v_3$}; \node[V] (v4) at (8.4,0) {$v_4$}; \draw[->] (v0) -- node[el, above]{edge 1} (v1); \draw[->] (v1) -- node[el, above]{edge 2} (v2); \draw[->] (v2) -- node[el, above]{edge 3} (v3); \draw[->] (v3) -- node[el, above]{edge 4} (v4); \foreach \i/\xe/\y in {1/2.1/-0.85, 2/4.2/-1.45, 3/6.3/-2.05, 4/8.4/-2.65} { \draw[br] (0,\y) -- (\xe,\y); \draw[br] (0,\y+0.09) -- (0,\y-0.09); \draw[br] (\xe,\y+0.09) -- (\xe,\y-0.09); \node[bl, right] at (\xe+0.15,\y) {round \i}; } \end{tikzpicture} $$ **Saving space.** The recurrence only ever reads row $k-1$, so we collapse the table to a single 1-D array $d[\cdot]$ updated in place, recovering the familiar form of Bellman-Ford as $n-1$ rounds of relaxing every edge. (In-place updates can only make estimates _better_ than the strict row-by-row schedule; the path-relaxation lemma tolerates the extra interleaved relaxations.) **Negative edges are fine**; only a negative _cycle_ breaks the theorem. ```algorithm caption: $\textsc{Bellman-Ford}(G, w, s)$ — space-saved; with cycle check number: 4 foreach vertex $v \in V$ do $v.d \gets \infty$ $v.\pi \gets \text{nil}$ $s.d \gets 0$ for $i \gets 1$ to $n - 1$ do // V-1 full-relaxation rounds foreach edge $(u, v) \in E$ do call $\textsc{Relax}(u, v, w)$ foreach edge $(u, v) \in E$ do // extra pass: detect neg cycle if $u.d + w(u, v) < v.d$ then return false // neg cycle reachable from s return true ``` **Detecting negative cycles.** After $n - 1$ rounds, if any edge can _still_ be relaxed, some walk was improved using $n$ edges — only possible if a **negative cycle** lets the cost descend without bound. So one extra pass serves as the test: relax everything once more, and any successful relaxation certifies a negative cycle reachable from $s$ (where "cheapest cost to reach a vertex" is no longer even well-defined).[^erickson-sp] The extra pass is a decision procedure, and it is both [sound and complete](/algorithms/foundations/what-is-an-algorithm): a relaxation can succeed only when a reachable negative cycle exists (soundness, no false alarm), and any such cycle forces some edge to relax on that pass (completeness, none is missed). Dijkstra entirely lacks that capability. The cost is $\Theta(V \cdot E)$: $\abs{V} - 1$ passes, each relaxing all $\abs{E}$ edges. > **Example (Tracing it).** On our digraph from $s$, the DP rows settle quickly. Row 1 > relaxes the source edges: $a.d = 10$, $b.d = 5$. Row 2 propagates one edge > further, setting $c.d = a.d + 1 = 11$ and $t.d = b.d + 2 = 7$, and tests the > negative edge $a \to b$, but $10 + (-2) = 8 > 5$, so $b$ keeps its cheaper > direct route. Row 3 settles $t.d = c.d + 4 = 15$ vs. the existing $7$, so no > change. The table has converged in fewer than $n-1 = 4$ rounds; a final pass > changes nothing, certifying no reachable negative cycle. Laid out as the DP table $\text{OPT}[k, v]$, the layering is plain: row $k$ holds the cheapest walk of at most $k$ edges, each row computed from the one above by a single full pass of relaxation. The entries that improved on each row are shaded; the table stops changing after row $2$, well within the $n-1 = 4$ bound: $$ % caption: The Bellman-Ford DP table $\text{OPT}[k, v]$ for the trace digraph. Row $k$ = % cheapest $s \rightsquigarrow v$ walk of $\le k$ edges; shaded cells improved % that round. Rows freeze after $k=2$. \begin{tikzpicture}[ cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small}, hdr/.style={draw=none, font=\small}, imp/.style={cell, fill=acc!18}] \definecolor{acc}{HTML}{2348F2} % corner + column headers (vertices) + row headers (round k) \node[hdr] at (0,0) {$k$}; \node[hdr] at (1,0) {$s$}; \node[hdr] at (2,0) {$a$}; \node[hdr] at (3,0) {$b$}; \node[hdr] at (4,0) {$c$}; \node[hdr] at (5,0) {$t$}; \node[hdr] at (0,-1) {$0$}; \node[hdr] at (0,-2) {$1$}; \node[hdr] at (0,-3) {$2$}; \node[hdr] at (0,-4) {$3$}; % k=0: only s reachable; shaded cells improved this round \node[imp] at (1,-1) {$0$}; \node[cell] at (2,-1) {inf}; \node[cell] at (3,-1) {inf}; \node[cell] at (4,-1) {inf}; \node[cell] at (5,-1) {inf}; % k=1 \node[cell] at (1,-2) {$0$}; \node[imp] at (2,-2) {$10$}; \node[imp] at (3,-2) {$5$}; \node[cell] at (4,-2) {inf}; \node[cell] at (5,-2) {inf}; % k=2 \node[cell] at (1,-3) {$0$}; \node[cell] at (2,-3) {$10$}; \node[cell] at (3,-3) {$5$}; \node[imp] at (4,-3) {$11$}; \node[imp] at (5,-3) {$7$}; % k=3 (frozen — no improvements) \node[cell] at (1,-4) {$0$}; \node[cell] at (2,-4) {$10$}; \node[cell] at (3,-4) {$5$}; \node[cell] at (4,-4) {$11$}; \node[cell] at (5,-4) {$7$}; \end{tikzpicture} $$ > **Remark (A special case worth knowing).** On a **DAG** there are no cycles at all, so > we can relax edges in _topological order_ (from the previous lesson) in a > single sweep, since every vertex's predecessors are finalized before it is reached. > This solves DAG shortest paths in $\Theta(V + E)$, and it works with negative > weights too. ::impl{algo="bellman_ford,dag_shortest_paths"} ## Floyd-Warshall: all pairs at once Sometimes we want $\delta(u, v)$ for _every_ pair of vertices, a full distance matrix. Running Bellman-Ford from each source costs $O(V^2 E)$, up to $\Theta(V^4)$ on dense graphs, but $\textsc{Floyd-Warshall}$ does better with a dynamic program parameterized not by edge count but by which vertices a path is _allowed to pass through_. > **Definition ($k$-limited distance).** Number the vertices $1, \dots, n$, and > let $d_{ij}^{(k)}$ be the minimum weight of any $i \rightsquigarrow j$ path > whose **intermediate** vertices (every vertex on the path except the endpoints > $i$ and $j$ themselves) all lie in $\set{1, \dots, k}$. The base case > $d_{ij}^{(0)}$ allows _no_ intermediates: it is $0$ if $i = j$, $w(i, j)$ if > the edge exists, and $\infty$ otherwise. The other extreme, $d_{ij}^{(n)}$, > allows every vertex, so $d_{ij}^{(n)} = \delta(i, j)$. The recurrence lifts $d^{(k-1)}$ to $d^{(k)}$ by a case split that is **exhaustive by construction**: a shortest path counted by $d_{ij}^{(k)}$ either uses vertex $k$ as an intermediate or it does not, and there is no third possibility. If it does not, its intermediates already lie in $\set{1, \dots, k-1}$ and it is counted by $d_{ij}^{(k-1)}$. If it does, then (assuming no negative cycles, we may take the path simple, so $k$ appears exactly once) $k$ splits the path into an $i \rightsquigarrow k$ half and a $k \rightsquigarrow j$ half, _neither of which contains $k$ in its interior_. Both halves have intermediates in $\set{1, \dots, k-1}$, and by optimal substructure each half is a shortest path of its own class, so their costs are exactly $d_{ik}^{(k-1)}$ and $d_{kj}^{(k-1)}$. Taking the better case: $$ d_{ij}^{(k)} = \min\!\parens{ d_{ij}^{(k-1)},\; d_{ik}^{(k-1)} + d_{kj}^{(k-1)} }. $$ $$ % caption: Why the recurrence is exhaustive. A shortest $i \rightsquigarrow j$ path with % intermediates in $\{1, \dots, k\}$ either avoids $k$ entirely — the % $d_{ij}^{(k-1)}$ case — or passes through $k$ exactly once, splitting into % halves $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ whose interiors use only vertices % below $k$. \begin{tikzpicture}[>=Stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \tikzset{V/.style={circle, draw, minimum size=7mm, font=\small, inner sep=0.5pt}, lb/.style={font=\scriptsize}} \node[V] (i) at (0,0) {$i$}; \node[V, draw=acc, thick, fill=acc!12] (k) at (3.1,1.6) {$k$}; \node[V] (j) at (6.2,0) {$j$}; \draw[->, draw=acc, thick] (i) to[bend left=15] node[lb, above left=-1pt]{via 1..k-1} (k); \draw[->, draw=acc, thick] (k) to[bend left=15] node[lb, above right=-1pt]{via 1..k-1} (j); \draw[->, dashed] (i) to[bend right=25] node[lb, below]{avoids k} (j); \end{tikzpicture} $$ Induction on $k$ turns this into correctness: $d^{(0)}$ is right by definition, and if $d^{(k-1)}$ holds every $(k-1)$-limited distance, the case split shows the recurrence computes every $k$-limited one. After round $n$, no restriction remains. Consider one round of the recurrence. Starting from $d^{(0)}$ — direct edges only — and admitting intermediates from $\set{1, 2}$ produces $d^{(2)}$: the entry $d_{13}$ drops from $8$ to $5$ via $1 \to 2 \to 3$, and the once-unreachable $d_{42}, d_{43}$ become finite by routing through vertex $1$ then $2$. The five matrices $d^{(0)},\dots,d^{(4)}$ below trace one round per permitted intermediate; the entries that improved in each round are shaded: $$ % caption: Floyd-Warshall, one matrix per round. $d^{(k)}$ uses only vertices % $\{1,\dots,k\}$ as intermediates; each round's pivot vertex $k$ is marked in % blue on the indices (its row and column drive that round's updates), and the % entries that improved when $k$ was admitted are shaded. $d^{(4)}$ holds the % all-pairs shortest distances. \begin{tikzpicture}[font=\small] \definecolor{acc}{HTML}{2348F2} % --- graph (top): the two diagonals are straight, forming an X; each weight % label hugs its own edge near the source node, so 8 and 7 can't be confused --- \begin{scope}[xshift=47mm, yshift=24mm, >=Stealth, every node/.style={circle, draw, minimum size=7mm, font=\scriptsize}, wt/.style={draw=none, font=\scriptsize, fill=white, inner sep=1pt}] \node (1) at (0,1.6) {$1$}; \node (2) at (2.2,1.6) {$2$}; \node (3) at (2.2,0) {$3$}; \node (4) at (0,0) {$4$}; \draw[->] (1) -- node[wt, above]{$3$} (2); \draw[->] (2) -- node[wt, right]{$2$} (3); \draw[->] (3) -- node[wt, below]{$1$} (4); \draw[->] (4) -- node[wt, left]{$2$} (1); \draw[->] (1) -- (3); \draw[->] (2) -- (4); \node[wt, fill=none] at (0.85,1.28) {$8$}; \node[wt, fill=none] at (0.34,0.52) {$7$}; \end{scope} % --- five matrices in a row; \hi marks the cells that improved this round --- \tikzset{ mlabel/.style={font=\footnotesize}, idx/.style={font=\tiny, gray}, sub/.style={font=\scriptsize, gray}, hi/.style={fill=acc!18}} \newcommand{\fwmat}[5]{% #1=xshift #2=k #3=highlight #4=rows #5=subtitle \begin{scope}[xshift=#1 mm] \node[mlabel] at (0.75,0.82) {$d^{(#2)}$}; \foreach \j/\x in {1/0,2/0.5,3/1.0,4/1.5} { \ifnum\j=#2 \node[idx, acc] at (\x,0.42) {$\j$};\else \node[idx] at (\x,0.42) {$\j$};\fi} \foreach \i/\y in {1/0,2/-0.45,3/-0.9,4/-1.35} { \ifnum\i=#2 \node[idx, acc] at (-0.42,\y) {$\i$};\else \node[idx] at (-0.42,\y) {$\i$};\fi} \foreach \hx/\hy in {#3} \fill[hi] (\hx-0.23,\hy-0.2) rectangle (\hx+0.23,\hy+0.2); \foreach \row/\y in {#4} \foreach \val [count=\ci from 0] in \row \node[font=\scriptsize] at (\ci*0.5,\y) {\val}; \node[sub] at (0.75,-1.82) {#5}; \end{scope}} \fwmat{0}{0}{}{{0,3,8,inf}/0,{inf,0,2,7}/-0.45,{inf,inf,0,1}/-0.9,{2,inf,inf,0}/-1.35}{direct edges} \fwmat{26}{1}{0.5/-1.35,1.0/-1.35}{{0,3,8,inf}/0,{inf,0,2,7}/-0.45,{inf,inf,0,1}/-0.9,{2,5,10,0}/-1.35}{via 1} \fwmat{52}{2}{1.0/0,1.5/0,1.0/-1.35}{{0,3,5,10}/0,{inf,0,2,7}/-0.45,{inf,inf,0,1}/-0.9,{2,5,7,0}/-1.35}{via 1,2} \fwmat{78}{3}{1.5/0,1.5/-0.45}{{0,3,5,6}/0,{inf,0,2,3}/-0.45,{inf,inf,0,1}/-0.9,{2,5,7,0}/-1.35}{via 1,2,3} \fwmat{104}{4}{0/-0.45,0/-0.9,0.5/-0.9}{{0,3,5,6}/0,{5,0,2,3}/-0.45,{3,6,0,1}/-0.9,{2,5,7,0}/-1.35}{via 1..4} \end{tikzpicture} $$ Three nested loops over $k$, $i$, $j$ evaluate this recurrence directly: the outer loop admits one intermediate vertex $k$ per round (exactly the five matrices above), and the inner two relax every pair against a route through it. ```algorithm caption: $\textsc{Floyd-Warshall}(W)$ — all-pairs shortest paths in $O(V^3)$ $d \gets W$ // $d_{ij}$: edge weight; $0$ on the diagonal, else $\infty$ for $k \gets 1$ to $n$ do // admit vertex $k$ as an intermediate for $i \gets 1$ to $n$ do for $j \gets 1$ to $n$ do if $d_{ik} + d_{kj} < d_{ij}$ then // routing through $k$ is shorter $d_{ij} \gets d_{ik} + d_{kj}$ return $d$ ``` The pseudocode quietly drops the superscripts and updates one matrix in place, and this needs a word of justification: during round $k$, could an entry $d_{ik}$ or $d_{kj}$ that the recurrence _reads_ have already been overwritten with a round-$k$ value? It could, but harmlessly, because row and column $k$ do not change during round $k$: $d_{ik}^{(k)} = \min\parens{d_{ik}^{(k-1)}, d_{ik}^{(k-1)} + d_{kk}^{(k-1)}} = d_{ik}^{(k-1)}$, since $d_{kk} = 0$ (and $\ge 0$ whenever no negative cycle exists). Reading "new" values is the same as reading old ones, so one $n \times n$ matrix suffices. **Running time.** The algebra is the shortest of the lesson: three nested loops of $n$ iterations each, with a constant-time comparison in the body: $n \cdot n \cdot n = \Theta(V^3)$ time and $\Theta(V^2)$ space. No priority queue, no per-edge bookkeeping: compact, cache-friendly, and a clean win on dense graphs.[^skiena-sp] It handles negative edges, and a negative entry on the diagonal ($d_{ii} < 0$) flags a negative cycle through $i$. For _sparse_ graphs with non-negative weights, running Dijkstra from every source costs $O(VE + V^2 \log V)$, which beats $\Theta(V^3)$ when $E \ll V^2$; Floyd-Warshall wins on dense inputs and on any input where its tiny constant factor and trivial implementation matter more than asymptotics. ::impl{algo="floyd_warshall"} ## Choosing an algorithm | Algorithm | Solves | Negative edges? | Time | | --- | --- | --- | --- | | BFS | SSSP, **unweighted** | n/a | $O(V + E)$ | | DAG relaxation | SSSP on a DAG | yes | $O(V + E)$ | | $\textsc{Dijkstra}$ | SSSP | **no** | $O(E + V\log V)$ | | $\textsc{Bellman-Ford}$ | SSSP, + cycle detection | yes | $O(V \cdot E)$ | | $\textsc{Floyd-Warshall}$ | **all-pairs** | yes | $O(V^3)$ | The decision tree is short: unweighted, use BFS; a DAG, relax in topological order; non-negative weights, use Dijkstra (the fastest for one source); negative edges possible, use Bellman-Ford and let it detect negative cycles; every pair at once, use Floyd-Warshall on dense graphs, or repeated Dijkstra ($O(VE + V^2\log V)$) when the graph is sparse and the weights non-negative. All five are disciplined applications of the same $\textsc{Relax}$ primitive; they differ only in _which edges they relax, and in what order_. ## Sparse all-pairs and what negative cycles buy you **Johnson's algorithm.** Floyd-Warshall's $\Theta(V^3)$ is fine on dense graphs but wasteful on sparse ones. Johnson's algorithm computes all-pairs shortest paths in $O(VE + V^2 \log V)$ — the cost of $V$ Dijkstra runs — _while still tolerating negative edges_.[^johnson] It uses a **reweighting** that removes the negatives without changing which paths are shortest. Add a dummy vertex $q$ with a zero-weight edge to every vertex, run Bellman-Ford once from $q$ to get a potential $h(v) = \delta(q, v)$, then reweight each edge to $$ w'(u, v) = w(u, v) + h(u) - h(v). $$ The triangle inequality $h(v) \le h(u) + w(u,v)$ makes every $w'(u,v) \ge 0$, and the $h(u) - h(v)$ terms telescope along any path, so a path's reweighted length differs from its true length by the constant $h(s) - h(t)$ — same ordering, same shortest paths. Now run Dijkstra from every source on the non-negative $w'$, and undo the shift. One Bellman-Ford pass establishes non-negativity; $V$ Dijkstra passes finish the job. (This is the same potential trick that underlies A\* from the previous lesson.) **SPFA and the practical Bellman-Ford.** In practice, few graphs force all $V-1$ Bellman-Ford rounds. The "shortest-path faster algorithm" keeps a queue of vertices whose estimate just improved and only relaxes out of those, often finishing in far fewer than $VE$ operations — though its worst case is still $\Theta(VE)$, so it is a constant-factor win, not an asymptotic one. Bellman-Ford also parallelizes cleanly: every edge in a round relaxes independently, which is why GPU shortest-path codes favor it over Dijkstra's inherently sequential extraction order. **What a negative cycle is worth.** Bellman-Ford's negative-cycle detector is useful in its own right: some problems ask for the cycle itself. In currency arbitrage, let each currency be a vertex and each exchange rate $r_{uv}$ an edge of weight $-\log r_{uv}$. A path's total weight is $-\log$ of the product of rates along it, so any cycle of negative total weight is a sequence of trades that multiplies the starting sum by more than $1$.[^arbitrage] Detecting arbitrage is Bellman-Ford's extra pass, and reconstructing the offending cycle from the predecessor pointers recovers the trades. $$ % caption: Arbitrage as a negative cycle. Each edge $u \to v$ carries weight % $w_{uv} = -\log r_{uv}$, so the cycle USD to EUR to GBP to USD has total weight % $w_1 + w_2 + w_3 = -\log(r_1 r_2 r_3)$; it is negative exactly when the product % of rates exceeds $1$, i.e. the loop is profitable. \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=9mm, font=\small}, wt/.style={font=\scriptsize, fill=white, inner sep=1.5pt}] \definecolor{acc}{HTML}{2348F2} \node[V] (u) at (0,0) {USD}; \node[V] (e) at (3.2,0.9) {EUR}; \node[V] (g) at (3.2,-0.9) {GBP}; \draw[->, acc, thick] (u) to[bend left=12] node[wt, above left]{$w_1$} (e); \draw[->, acc, thick] (e) -- node[wt, right]{$w_2$} (g); \draw[->, acc, thick] (g) to[bend left=12] node[wt, below left]{$w_3$} (u); \end{tikzpicture} $$ The pattern generalizes: minimum-mean-cycle, difference constraints (systems of $x_j - x_i \le c$ solved by a single Bellman-Ford), and deadlock detection all reduce to shortest paths with negative edges. Whenever a problem's "cost" is a sum you want to drive as low as possible around a loop, Bellman-Ford's cycle machinery is the tool. ## Takeaways - Shortest paths rest on **relaxation** plus two structural facts: the **triangle inequality** and **optimal substructure**. - $\textsc{Dijkstra}$ greedily finalizes the closest frontier vertex; the cut argument shows an extracted vertex's estimate is already exact. Correct _only_ for non-negative weights; a single negative edge lets a cheap route arrive after its target is frozen. $O(E + V\log V)$ with a Fibonacci heap. - $\textsc{Bellman-Ford}$ _is a dynamic program_: $\text{OPT}(k, v)$ = cheapest $s \rightsquigarrow v$ walk of $\le k$ edges, and one DP row = one pass of relaxing all edges. Shortest paths need $\le \abs{V}-1$ edges (short-circuit any cycle), so $\abs{V}-1$ rounds suffice; one extra round **detects negative cycles**. Slower at $\Theta(V \cdot E)$ but handles negative edges. - On a **DAG**, relaxing in topological order solves SSSP in $\Theta(V + E)$. - $\textsc{Floyd-Warshall}$ computes **all-pairs** shortest paths in $\Theta(V^3)$ via a dynamic program over intermediate vertices. [^clrs-relax]: **CLRS**, Ch. 24 & 25 — Single-Source and All-Pairs Shortest Paths — relaxation, the triangle inequality, and optimal substructure. [^erickson-sp]: **Erickson**, Ch. 8 & 9 — Shortest Paths — Bellman-Ford's extra relaxation pass detecting a negative cycle. [^skiena-sp]: **Skiena**, §6 — Weighted Graph Algorithms — Floyd-Warshall's $\Theta(V^3)$ all-pairs dynamic program. [^johnson]: **Johnson, D. B.** (1977), "Efficient algorithms for shortest paths in sparse networks," _Journal of the ACM_ 24(1), 1–13 — reweighting for all-pairs shortest paths on sparse graphs. [^arbitrage]: **Cormen, Leiserson, Rivest & Stein**, _Introduction to Algorithms_ (CLRS), Problem 24-3 — currency arbitrage as a negative-weight cycle under $-\log$ rates.