Floyd-Warshall Visualization for Coding Interviews
All-pairs shortest path; O(V³) DP over intermediate vertices.
Concept
Floyd-Warshall solves all-pairs shortest paths with a three-line triple loop and an in-place O(V^2) matrix. Compared to running Dijkstra V times or Johnson's algorithm, Floyd-Warshall is almost insultingly simple: no heap, no priority queue, no adjacency list gymnastics, just dynamic programming over paths by their allowed intermediate vertices. The tradeoff is the cube: runtime is O(V^3) and space is O(V^2), which makes it practical for dense graphs up to a few hundred vertices and impractical beyond that. It handles negative edges out of the box, detects negative cycles by checking the diagonal, and produces not just distances but the transitive closure if you reinterpret the recurrence boolean-wise. The algorithm is also the cleanest vehicle for understanding a key dynamic-programming pattern: relax over "allowed intermediate vertices" rather than over "path length", which is the lens Bellman-Ford uses.
How it works
Let dist[i][j] initially hold the direct edge weight from i to j (0 on the diagonal, infinity if no edge). The recurrence is dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) evaluated for k from 0 to n-1 in the outermost loop. Read the k loop as "now we allow k as an intermediate": after the k-th iteration completes, dist[i][j] holds the shortest path from i to j that uses only vertices 0..k as intermediates. Inducting up to k = n-1 gives shortest paths over the entire vertex set. Because each update only reads and writes the same matrix, the algorithm runs in place; there is no need for a separate "previous-k" layer, which is a common thing to over-engineer. To reconstruct actual paths, maintain a next[i][j] matrix updated whenever dist[i][j] is improved, then walk next repeatedly from source to target. To detect negative cycles, check whether any dist[i][i] has become negative at the end - a vertex that can reach itself at negative cost implies a cycle on its path. Be careful with overflow: use a large but bounded sentinel and guard the addition against INF.
Implementation
public class FloydWarshall {
public static final long INF = Long.MAX_VALUE / 4;
/**
* In-place all-pairs shortest paths.
* dist must be initialized so that:
* dist[i][i] = 0
* dist[i][j] = edge weight if a direct edge exists
* dist[i][j] = INF otherwise
*
* Returns true if a negative-weight cycle was detected (some dist[i][i] < 0 after).
*/
public static boolean floydWarshall(long[][] dist, int n) {
// Relax over intermediate vertex k in the outermost loop.
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (dist[i][k] >= INF) continue; // prune rows that cannot reach k
for (int j = 0; j < n; j++) {
if (dist[k][j] >= INF) continue; // prune columns unreachable from k
long cand = dist[i][k] + dist[k][j];
if (cand < dist[i][j]) {
dist[i][j] = cand;
}
}
}
}
// Negative cycle iff some vertex can reach itself with negative total cost.
for (int i = 0; i < n; i++) {
if (dist[i][i] < 0) return true;
}
return false;
}
/** Path-reconstruction variant: also fills next[i][j] with the next hop on the shortest i->j path. */
public static void floydWithPaths(long[][] dist, int[][] next, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
next[i][j] = (dist[i][j] < INF && i != j) ? j : -1;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (dist[i][k] >= INF) continue;
for (int j = 0; j < n; j++) {
if (dist[k][j] >= INF) continue;
long cand = dist[i][k] + dist[k][j];
if (cand < dist[i][j]) {
dist[i][j] = cand;
next[i][j] = next[i][k];
}
}
}
}
}
}Complexity
- Time:
O(V^3) - Space:
O(V^2)
Common pitfalls
- Using Integer.MAX_VALUE or Long.MAX_VALUE as INF and overflowing on dist[i][k] + dist[k][j].
- Putting the k loop in the wrong position; k must be outermost for the DP invariant to hold.
- Applying Floyd-Warshall to a graph with thousands of vertices - V^3 gets painful fast.
- Forgetting to set dist[i][i] = 0 on initialization, which corrupts the whole matrix.
- Claiming a negative-cycle check when you only looked at a single row instead of the whole diagonal.
Key design decisions & trade-offs
- When to choose over Dijkstra — Chosen: Dense graphs with V up to a few hundred, or when negative edges are present. Running Dijkstra V times costs O(V*(V+E) log V); for dense graphs that is O(V^3 log V), worse than FW's O(V^3).
- Matrix vs list representation — Chosen: Adjacency matrix. The algorithm is inherently O(V^2) in memory and needs random access to dist[i][j]; a matrix is the natural container.
- Path reconstruction storage — Chosen: next[][] matrix instead of parent per source. A single V^2 int matrix lets you walk any i -> j path in O(L); storing V parent arrays would cost the same but be clumsier.
Practice problems
Interview follow-ups
- Transitive closure via boolean Floyd-Warshall (OR of reachability instead of min of distance).
- Minimax / maximin path matrices by swapping min/+ for max/min (algebraic semiring reformulation).
- Johnson's algorithm for sparse graphs with negative edges - reweight then Dijkstra V times.
- Incremental updates when an edge is added or a vertex is inserted.
- Using FW to compute the diameter and eccentricity of a graph in one pass.
Why it matters
Floyd-Warshall is a core part of the Graphs toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".