1. Floyd-Warshall: Intermediate Vertex Set Induction
Define $d^{(k)}[i][j]$ as the minimum weight of any path from $i$ to $j$ whose intermediate vertices belong strictly to the prefix set $\{0, 1, \dots, k\}$. Considering whether vertex $k$ is used as an intermediate stop along the shortest path from $i$ to $j$ yields the recurrence:
$$d^{(k)}[i][j] = \min\Big(d^{(k-1)}[i][j],\; d^{(k-1)}[i][k] + d^{(k-1)}[k][j]\Big)$$Why can we overwrite a single 2D matrix $d[i][j]$ in-place without corrupting phase $k$'s dependencies? Notice that during phase $k$, $d[i][j]$ reads $d[i][k]$ and $d[k][j]$. In phase $k$ itself, $d[i][k]$ is updated to $\min(d[i][k], d[i][k] + d[k][k])$. As long as no negative cycle passes through $k$ ($d[k][k] \ge 0$), $d^{(k)}[i][k] == d^{(k-1)}[i][k]$ and $d^{(k)}[k][j] == d^{(k-1)}[k][j]$! Thus in-place updates are exact.
Negative Cycle Detection: A vertex $u$ lies on a negative cycle if and only if after completion (or during execution) its diagonal entry satisfies $d[u][u] < 0$.
2. Johnson's Potential Reweighting Theorem (1977)
How can we eliminate negative edge weights without changing which path between $u$ and $v$ is shortest? (Simply adding a constant $+C$ to every edge is a classic blunder: it penalizes a 5-edge path by $+5C$ and a 2-edge path by $+2C$, changing the optimal path!)
Instead, assign every vertex $v \in V$ a scalar potential $h(v) \in \mathbb{R}$ and define the reweighted edge cost:
$$w_h(u, v) = w(u, v) + h(u) - h(v)$$Along any path $P = \langle v_0, v_1, \dots, v_k \rangle$ from $v_0 = u$ to $v_k = v$, the intermediate potentials telescope and cancel completely:
$$w_h(P) = \sum_{i=1}^k \big(w(v_{i-1}, v_i) + h(v_{i-1}) - h(v_i)\big) = w(P) + h(u) - h(v)$$Because $h(u) - h(v)$ depends only on the endpoints $(u, v)$ and not on the path $P$, every path from $u$ to $v$ shifts by the exact same constant $h(u) - h(v)$! To guarantee $w_h(u, v) \ge 0$ for all $(u, v) \in E$, we need $h(v) - h(u) \le w(u, v)$—which is satisfied by setting $h(v) = \delta(s^*, v)$ from a single Bellman-Ford run starting at a virtual super-source $s^*$!
Witness negative cycles on the V-th relaxation round of Bellman-Ford, inspect Floyd-Warshall’s in-place DP matrix D^(k)[i][j] = min(D[i][j], D[i][k]+D[k][j]), and reweight negative edges to non-negative via Johnson potentials w_hat(u,v) = w(u,v) + h(u) - h(v) ≥ 0.
Invariant & State
In Floyd-Warshall's loop order for k ... for i ... for j, the inner loop over j streams sequentially across row d[i][0..V-1] and row d[k][0..V-1] while holding d[i][k] in a scalar register. Compilers (-O3 -mavx2) auto-vectorize this inner loop using VPMINSD / VPADDD SIMD instructions, processing 8 distances per clock cycle!
Complexity Matrix
| APSP Algorithm | Negative Edges? | Time Complexity | Space Complexity |
|---|---|---|---|
| $V \times$ Dijkstra | No ($w \ge 0$ only) | O(V E + V² log V) | O(V²) output |
| Floyd-Warshall DP | Yes (detects $d[i][i] < 0$) | O(V³) | O(V²) |
| Johnson's Algorithm | Yes (1 BF + $V$ Dijkstras) | O(V E + V² log V) | O(V² + E) |
| Warshall Bitset Transitive Closure | Unweighted Reachability | O(V³ / 64) | V² / 8 bytes |
Production Implementation: Floyd-Warshall & Johnson's Potential Reweighting
#include <vector>
#include <algorithm>
#include <limits>
void floydWarshall(int n, std::vector<std::vector<long long>>& dist) {
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
if (dist[i][k] >= INF) continue; // Crucial overflow guard + branch skip!
for (int j = 0; j < n; ++j) {
if (dist[k][j] < INF) {
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}for i ... for j ... for k in Floyd-WarshallPermuting the loops of Floyd-Warshall to place k on the inside (for i ... for j ... for k) is one of the most notorious bugs in competitive and production programming: it only considers paths of length $\le 2$ (single intermediate hop $i \to k \to j$) or corrupts transitive dependencies across multi-hop paths! The intermediate vertex k must always be the outermost loop.