Floyd-Warshall — all-pairs shortest paths, O(V³)

WHAT is the problem?

The output is a full $V \times V$ matrix of distances (and optionally a matrix to reconstruct paths).

WHY a new algorithm (and not just run Dijkstra V times)?

• Running Dijkstra from every source: $O(V \cdot (E + V\log V))$ — but breaks with negative edges.
• Running Bellman-Ford from every source: $O(V \cdot VE) = O(V^2 E)$, which for dense graphs ($E \approx V^2$) is $O(V^4)$.
• Floyd-Warshall: a clean $O(V^3)$, handles negative edges, and is 5 lines of code. For dense graphs and small $V$ (say $V \le 400$) it's the king.

HOW: derive it from scratch (dynamic programming)

Let's define a subproblem carefully — this is the heart of it.

Base case ($k=0$): no intermediate vertices allowed, so the only legal paths are single edges. $d_0(i,j) = \begin{cases} 0 & i = j \\ w(i,j) & (i,j)\in E \\ +\infty & \text{otherwise}\end{cases}$

Transition — the key insight. Consider the shortest path from $i$ to $j$ using intermediates $\{1,\dots,k\}$. Vertex $k$ is either used by this path or not:

• $k$ is NOT used → the path only uses $\{1,\dots,k-1\}$, so its length is $d_{k-1}(i,j)$.
• $k$ IS used → because there are no negative cycles, the optimal path visits $k$ exactly once. Split it at $k$: a piece $i \to k$ and a piece $k \to j$, each using only $\{1,\dots,k-1\}$ as intermediates. So its length is $d_{k-1}(i,k) + d_{k-1}(k,j)$.

We take the better of the two:

Collapsing to a 2D array (the in-place trick)

The recurrence updates layer $k$ from layer $k-1$. We can overwrite the same matrix $d$. Is that safe? When computing $d[i][j]$ using $d[i][k]+d[k][j]$:

• $d[i][k]$ in the new layer = $\min(d[i][k], d[i][k]+d[k][k])$. Since $d[k][k]=0$ (no negative cycle), it's unchanged.
• Same for $d[k][j]$.

So overwriting does not corrupt the values we read. Hence one $V\times V$ matrix suffices.

def floyd_warshall(n, dist):       # dist[i][j] = weight or INF, dist[i][i]=0
    for k in range(n):             # k = intermediate vertex being "unlocked"
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Detecting negative cycles

After running, check the diagonal. If any $d(i,i) < 0$, then $i$ lies on a negative cycle (you found a path from $i$ back to $i$ cheaper than staying put).

Path reconstruction

Keep a next[i][j] (or parent[i][j]) matrix. Initialize next[i][j] = j for each edge. Whenever you relax through $k$, set next[i][j] = next[i][k]. To rebuild $i\to j$: follow next until you reach $j$.

Worked Example 1 — a tiny 3-node graph

Vertices $0,1,2$. Edges: $0\to1 = 4$, $0\to2 = 11$, $1\to2 = 2$. No others.

Initial matrix ($\infty$ shown as $\cdot$):

Unlock $k=0$: any path improved by going through 0? Nothing points into 0, so no change. Why this step? $d[i][0]=\infty$ for $i\ne 0$, so $d[i][0]+d[0][j]$ is huge.

Unlock $k=1$: check $d[0][2]$ vs $d[0][1]+d[1][2] = 4+2 = 6 < 11$. Update $d[0][2]=6$. Why this step? Now route $0\to1\to2$ is legal because 1 is unlocked.

Unlock $k=2$: 2 has no outgoing edges, no improvements.

Final $d[0][2]=6$. ✔

Worked Example 2 — negative edge (where Dijkstra fails)

Vertices $0,1,2$. Edges: $0\to1=4$, $0\to2=5$, $1\to2=-3$.

Initial: $d[0][1]=4,\ d[0][2]=5,\ d[1][2]=-3$.

$k=1$: $d[0][2]$ vs $d[0][1]+d[1][2]=4+(-3)=1 < 5$ → update $d[0][2]=1$. Why this step? The negative edge $1\to2$ makes the detour through 1 cheaper — Floyd-Warshall handles it naturally since min doesn't care about edge sign (as long as no negative cycle).

Final $d[0][2]=1$. Dijkstra would have wrongly committed to $5$.

Worked Example 3 — negative cycle detection

Edges: $0\to1=1,\ 1\to2=-1,\ 2\to0=-1$. Cycle total $=1-1-1=-1<0$.

After running, $d[0][0]$ relaxes to $1+(-1)+(-1) = -1 < 0$. The diagonal goes negative → negative cycle detected. Why this step? The diagonal $d[i][i]$ starts at 0; only a negative loop back to $i$ can push it below 0.

Active Recall

Connections

• Dijkstra's Algorithm — single-source, non-negative weights only
• Bellman-Ford — single-source, handles negatives, detects negative cycles
• Dynamic Programming — Floyd-Warshall is layered DP over intermediate sets
• Johnson's Algorithm — APSP for sparse graphs, reweights then runs Dijkstra
• Transitive Closure — same loop structure with OR instead of min (Warshall's algorithm)
• Negative Cycles — detection via the diagonal

Concept Map

Hinglish (regional understanding)