Floyd-Warshall Algorithm

Given a directed graph with V vertices (0 .. V-1) and edges edges[i] = [u, v, w] with non-negative weight w, return the all-pairs shortest distance matrix D, where D[i][j] is the shortest distance from i to j (0 when i == j, -1 if j is unreachable from i).

Hints

· Stuck? Reveal one nudge at a time.

You need every pair's distance, so think all-pairs, not single-source.

For each intermediate vertex k, check if routing i→k→j is shorter.

Three nested loops with k outermost: D[i][j] = min(D[i][j], D[i][k] + D[k][j]).

Common doubts

The invariant is 'shortest paths using intermediates 0..k'; you must fully incorporate each k before moving on, which requires k outside i and j.

On dense graphs (E ≈ V²) it's simpler and comparable, and it handles negative edges, which Dijkstra can't.

If any diagonal entry D[i][i] becomes negative, i lies on a negative cycle.

Interview follow-ups

· What an interviewer asks next.

Keep a 'next' (or 'via') matrix updated whenever you relax, then trace it.

Seed both D[u][v] and D[v][u] from each edge.

Fun facts

Floyd-Warshall is dynamic programming over the set of allowed intermediate vertices.
Its transitive-closure cousin (replace min/+ with OR/AND) computes reachability.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 3, edges = [[0,1,3],[1,2,1],[0,2,10]]
Output: [[0,3,4],[-1,0,1],[-1,-1,0]]
0→1→2 (4) beats the direct 0→2 (10); rows 1 and 2 can't reach earlier vertices.

Example 2

Input: V = 2, edges = [[0,1,5]]
Output: [[0,5],[-1,0]]
Only 0→1 exists; 1 can't reach 0.

Constraints

- 1 <= V <= 100 - 0 <= edges.length <= V*(V-1) - 1 <= w <= 10^4 - edges are directed

When you need the distance between every pair of vertices, Floyd-Warshall is the compact answer. Build a V × V matrix seeded with direct edge weights (and 0 on the diagonal), then, for each vertex k in turn, ask: does routing through k shorten any pair? — D[i][j] = min(D[i][j], D[i][k] + D[k][j]). After trying all k, D holds every shortest distance. Three nested loops, O(V³).

The brute alternative runs a single-source shortest path from each vertex (here Dijkstra, since weights are non-negative): V runs of O((V+E) log V). Floyd-Warshall wins for dense graphs and is far simpler to write; it also naturally handles negative edges (and detects negative cycles via a negative diagonal).

Prerequisites

Before you start

· Concepts used directly in the solution.

Intermediate vertex. try each k between i and j.

Triangle relaxation. D[i][j] via D[i][k] + D[k][j].

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“All pairs or single source?”

All pairs — a full V×V matrix.

“Unreachable and self?”

-1 for unreachable, 0 on the diagonal.

The ideal opening — say it like this

I build a distance matrix from the edges, then for each intermediate k relax every pair via D[i][k] + D[k][j].

After all k, the matrix holds all-pairs shortest distances — O(V^3).

Understand the problem

Worked example — V = 3, edges [[0,1,3],[1,2,1],[0,2,10]]

via k=1: D[0][2] = min(10, D[0][1]+D[1][2]) = min(10, 4) = 4
D[0] = [0, 3, 4]

Key observations

1Aha

k as an intermediate

Trying every k covers all possible detours.

2Aha

Triangle relaxation

D[i][j] = min(D[i][j], D[i][k] + D[k][j]).

3Aha

O(V³), simple to code

Three loops; ideal for dense graphs and all-pairs queries.

Brute force vs optimal

	Dijkstra per source	Floyd-Warshall
Idea	run SSSP from each vertex	relax every pair via each intermediate
Time	O(V·(V+E) log V)	O(V³)
Best for	sparse graphs	dense / all-pairs

Both produce the same distance matrix. Full code is in the Approaches selector below.

Summary

Key takeaway

Floyd-Warshall: seed a distance matrix from edges, then for each intermediate k relax every pair with D[i][k] + D[k][j]. O(V³), all pairs, dead simple.

for k: for i: for j: D[i][j] = min(D[i][j], D[i][k] + D[k][j])