Shortest Path

01 / The shared mechanism

Find the shortest route from a source to every other node. The mechanism splits by what the edges carry — uniform costs collapse to BFS, non-negative weights need a priority queue (Dijkstra), negatives demand relaxation rounds (Bellman-Ford), and full transit tables fall to Floyd-Warshall.

01 / The one-sentence essence

After processing intermediate k, dist[i][j] is the shortest path from i to j that only uses nodes in {0, …, k} as intermediates — so a triple loop over (k, i, j) sweeps every pair into its final shortest distance.

Problemall-pairs shortest path on a weighted graphGraphdiamondV4

∞

Graph has 4 nodes and 8 directed edges. Initial dist: diagonal = 0, edges → their weight, the rest ∞.

step

0 / 137

—

(i, j)

—

last update

—

0 / 137

Pick a preset above — Floyd-Warshall is all-pairs, so there is no source to choose.

02 / The pattern signature

# Floyd-Warshall — all-pairs shortest pathdist[i][j] ← ∞ for all i, jdist[i][i] ← 0 for all idist[u][v] ← w for each edge (u, v, w)# triple loop: k outermostfor k in [0, V):for i in [0, V):for j in [0, V):if dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] ← dist[i][k] + dist[k][j]# after the k-th iteration, k is the highest intermediate allowed

03 / When to recognize this pattern

"all-pairs shortest path"

You need distances between every pair of nodes, not just from one source. Running Dijkstra from each node is O(V · (V + E) log V); Floyd-Warshall does it in O(V³) with a two-line inner body.

"small dense graph"

V is tiny (a few hundred at most). The cubic cost dominates and the constant factor is unbeatable — Floyd is a few array reads and a comparison in the hot loop.

"transitive closure / reachability matrix"

Replace + with OR and min with AND; the same triple loop computes which pairs are connected at all. Same shape as the shortest-path case, different semiring.

"chained ratios / multiplicative paths"

Whenever the "path cost" composes via some associative operator (multiply ratios, AND bits, max of mins), Floyd's three-line update generalizes — swap the operator, keep the structure.

04 / Common pitfalls

Putting k anywhere but the outermost loop.

The DP invariant — "dist[i][j] uses only intermediates in {0…k}" — only holds because k is finalized for every (i, j) before we move on. Move the k loop inside and you start mixing partial answers with finished ones; the result is wrong.

ii.

Treating ∞ + x as a real number.

In real code, INT_MAX + w overflows. Use a sentinel like 1e9, or guard with if dist[i][k] != ∞ and dist[k][j] != ∞ before adding. The visualization here uses ∞ directly to keep the matrix readable.

iii.

Forgetting that negative cycles break the answer.

With negative edges Floyd is still correct as long as no negative cycle is reachable. A negative cycle shows up as dist[i][i] < 0 for some i after the algorithm — check the diagonal to detect it.

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Find the City With the Smallest Number of Neighbors at a Threshold Distance— LC 1334medium→02Course Schedule IV— LC 1462medium→03Evaluate Division— LC 399medium→04Design Graph With Shortest Path Calculator— LC 2642hard→

— / When to use which

unweighted BFS

Use when every edge has the same cost — 1 step = 1 edge.

grid · maze · O(V + E)

Dijkstra

Use when edge weights are non-negative.

priority queue · O((V + E) log V)

Bellman-Ford

Use when weights can go negative, or you need cycle detection.

V−1 relax rounds · O(V · E)

Floyd-Warshall

Use when you need all-pairs distances, not just single-source.

DP via intermediates · O(V³)