Floyd-Warshall algorithm - DSA Learning Guide

Overview

Floyd-Warshall computes the shortest distance between every pair of vertices in O(V^3). It is dynamic programming over intermediate nodes: after processing node k, dist[i][j] is the shortest path from i to j that only uses nodes 0..k as stops in between.

The core is three nested loops and one line: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). It handles negative edges (not negative cycles) and is ideal for small, dense graphs (V up to a few hundred) where you need many pairwise queries.

Adding hub airports one at a time

First you only know direct flights. Then you allow connections through hub 1 and update every route that gets cheaper. Then through hub 2, and so on. After allowing every airport as a hub, every route price is optimal.

When to use it

All-pairs shortest paths with V roughly <= 400.
Many queries of 'distance from i to j' on a fixed graph.
Transitive closure: can i reach j at all?
Graphs with negative edges but no negative cycles.

Problem patterns it solves

All-pairs distances with a threshold

Recognize it when: count cities reachable within a distance from each city.

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Transitive closure

Recognize it when: is a course a prerequisite of another, directly or indirectly.

1462. Course Schedule IV
399. Evaluate Division

Minimum conversion cost

Recognize it when: cost to convert any character or item to another through chains.

2976. Minimum Cost to Convert String I

Where it is used in real software

Distance tables

Precomputing travel times between every pair of warehouses or offices for planning tools.

Network analysis

Computing closeness and betweenness metrics on small networks.

Relational reasoning

Computing reachability (transitive closure) of 'is-a' or dependency relations.

Key terms

dist[i][j]: Current best distance from i to j.
Intermediate node k: The node allowed as a new stop in this phase.
Transitive closure: reach[i][j] = true if any path exists.
Negative cycle signal: dist[i][i] < 0 after the algorithm.

How it works, step by step

1
Initialize the matrix
dist[i][i] = 0, dist[i][j] = edge weight, otherwise Infinity.
2
Outer loop over k
k must be the outermost loop; it defines which nodes may be used as stops.
3
Try going through k
For every i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
4
Check negative cycles
Any dist[i][i] < 0 means i is on a negative cycle.

Three nodes, adding intermediates

Edges: 0->1 = 4, 1->2 = 1, 0->2 = 7

Phase	dist[0][2]	Reason
Direct edges	7	only the edge 0->2
k = 0	7	no path improves by stopping at 0
k = 1	5	dist[0][1] + dist[1][2] = 4 + 1 = 5 < 7
k = 2	5	stopping at 2 cannot help reach 2

NOWPhase: Direct edges | dist[0][2]: 7 | Reason: only the edge 0->2

After all phases, dist[0][2] = 5 via node 1. The same update ran for every pair simultaneously.

Implementation

1function floydWarshall(n, edges) {2  const dist = Array.from({ length: n }, (_, i) =>3    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)),4  );5  for (const [u, v, w] of edges) dist[u][v] = Math.min(dist[u][v], w);6 7  for (let k = 0; k < n; k++) {8    for (let i = 0; i < n; i++) {9      if (dist[i][k] === Infinity) continue;10      for (let j = 0; j < n; j++) {11        if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];12      }13    }14  }15  return dist;16}17 18// 1334. City with the fewest neighbors within a threshold19function findTheCity(n, edges, threshold) {20  const undirected = edges.flatMap(([u, v, w]) => [[u, v, w], [v, u, w]]);21  const dist = floydWarshall(n, undirected);22  let bestCity = -1, bestCount = Infinity;23  for (let i = 0; i < n; i++) {24    const count = dist[i].filter((d, j) => j !== i && d <= threshold).length;25    if (count <= bestCount) { bestCount = count; bestCity = i; } // ties: larger index26  }27  return bestCity;28}

Complexity and performance

TimeO(V^3)

Three nested loops.

SpaceO(V^2)

Distance matrix (in place).

Practical limitV ~ 400-500

About 10^8 operations.

Trade-offs

vs Dijkstra from every node

V runs of Dijkstra cost O(V (V + E) log V), better for large sparse graphs. Floyd-Warshall is simpler and better for small dense graphs.

Memory

The V x V matrix is fine for hundreds of nodes but impossible for millions.

Variants and related techniques

Path reconstruction

Keep next[i][j]; when relaxing through k, set next[i][j] = next[i][k].

Minimax / maximin paths

Replace + and min with max and min to compute bottleneck paths.

Common mistakes

Putting k in an inner loop.
Fix: k must be the outermost loop, or the DP order is wrong.
Overflow with MAX_VALUE in Java.
Fix: Use a large sentinel like 1e9 or check for infinity before adding.
Forgetting duplicate edges.
Fix: Keep the minimum weight when multiple edges connect the same pair.

Interview questions

Why must k be the outer loop?

The DP state after phase k means 'using only nodes 0..k as intermediates'. All pairs must be updated for one k before allowing the next node as a stop.

When would you choose Floyd-Warshall over Dijkstra?

When you need all-pairs distances on a small or dense graph, or when there are negative edges without negative cycles.

Practice problems

Problem	Difficulty	What it trains
1334. Find the City With the Smallest Number of Neighbors	Medium	All-pairs with threshold.
1462. Course Schedule IV	Medium	Transitive closure.
399. Evaluate Division	Medium	Multiplicative closure.
2976. Minimum Cost to Convert String I	Medium	26 x 26 distances.