What does Floyd-Warshall compute, and what are its time and space complexities?
answer
- Not one source — every source
- The answer is a square matrix
- Three nested loops over the vertices
- Cost depends on V only, never on E
- Cube for time, square for space
basics
~10 sFloyd-Warshall computes the shortest-path distance between every ordered pair of vertices in a single run, not from one source. It costs O(V^3) time through three nested loops and O(V^2) space for the distance matrix.
solid answer
~40 sFloyd-Warshall is an all-pairs shortest-path algorithm: one run fills a `V x V` matrix where entry `D[i][j]` is the cheapest cost to get from `i` to `j`. It is dynamic programming over intermediate vertices — the outer loop walks a candidate waypoint `k`, and the two inner loops ask, for every pair, whether routing through `k` is cheaper than what is already recorded. That gives O(V^3) time and O(V^2) space, both independent of edge count: the algorithm touches the matrix, not an edge list, so a sparse graph costs exactly as much as a dense one. The matrix is initialised with zero on the diagonal, the direct edge weight where an edge exists, and infinity elsewhere. Once built, any pairwise distance is an O(1) lookup.
go deeper
Be ready to say in one breath what it produces (every pairwise distance, in a matrix), the two complexities, and that it is a different question from single-source search. Knowing the initialisation values is a cheap way to sound like you have written it.
Explain why the bound is O(V^3) with no E in it, and describe the state the matrix holds part-way through a run rather than only at the end. Be able to say how space stays O(V^2) despite the algorithm having a third dimension in its recurrence.
Show that you reach for this only when the workload really is all-pairs and the vertex count is small, and that you know it produces costs, not routes, until you add the second matrix. Interviewers listen for whether you notice the E-independence cuts both ways.
Own the framing question: is the workload genuinely all-pairs, or is it many single-source queries that a cache could serve? The answer decides whether an O(V^3) precompute is an asset or a batch job nobody can afford to rerun.
## What "all-pairs" means Most shortest-path questions are *single-source*: given one starting vertex, what is the cheapest route to each of the others. Floyd-Warshall answers a different question — for **every** ordered pair `(i, j)`, what is the cheapest route from `i` to `j`. The output is not a list or a tree but a square matrix `D` of size `V x V`, where `D[i][j]` is that cost. On a directed graph `D[i][j]` and `D[j][i]` are generally different numbers, which is why "ordered pair" matters. ## The state, and why it is the whole algorithm The dynamic-programming state is: *the cheapest cost from `i` to `j` using only vertices from some allowed set as intermediate stops.* Endpoints `i` and `j` are always allowed; the set restricts what may appear **strictly between** them. Floyd-Warshall grows that permitted set one vertex at a time. Before any iteration the permitted set is empty, so `D[i][j]` can only be a direct edge. After processing waypoint `k`, the permitted set is `{0, 1, ..., k}`, and after the last waypoint it is every vertex — at which point the entries are unrestricted shortest distances. Each step is a two-way choice: for a pair `(i, j)` and a newly permitted waypoint `k`, either the best route still avoids `k`, in which case the stored value stands, or it passes through `k` exactly once, in which case its cost is the best `i`-to-`k` cost plus the best `k`-to-`j` cost, both already computed under the smaller permitted set. Take the smaller of the two. That single comparison, run for every `(i, j)` and every `k`, is the entire algorithm. ## Initialisation - `D[i][i] = 0` — staying put is free (assuming no negative self-loop). - `D[i][j] = w(i, j)` when a direct edge exists. With parallel edges, keep the cheapest. - `D[i][j] = INF` otherwise, meaning "no route known yet". Treat `INF + anything` as `INF` so an unreachable pair is never improved by an imaginary route through another unreachable pair. ## Where the costs come from Three loops of length `V` give exactly `V^3` iterations, each doing one addition and one comparison. There is no priority queue, no visited set, no edge scan — just arithmetic over a matrix. That is why the bound is **O(V^3) regardless of E**: a graph with 400 vertices and 400 edges costs the same as one with 400 vertices and 160,000 edges. It is also why the constant factor is unusually small for a graph algorithm, which matters more than the exponent at modest `V`. Space is O(V^2) for the matrix itself. Note the standard implementation updates `D` in place across waypoints rather than keeping one matrix per value of `k` — that in-place update is safe and is what keeps space at O(V^2) instead of O(V^3). ## What it does *not* give you for free The matrix stores **costs**, not routes. If you also need the actual sequence of vertices, carry a second `V x V` matrix that records, for each pair, the next hop (or the last intermediate vertex) on the current best route, updated whenever a distance improves. That is another O(V^2) of space and no extra asymptotic time, and the path is then reconstructed by walking that matrix hop by hop. ## The reflex to build When a problem says *every pair* and the vertex count is small — a few hundred — Floyd-Warshall is the shortest correct thing you can write, and its output turns every later distance question into an O(1) array read. When the problem names a single start vertex, or when the vertex count is large, this is the wrong tool and the answer lies with single-source methods. Recognising which of those two questions you were asked is the point of knowing the algorithm at all.
- The matrix gives costs. How do you recover the actual route between two vertices?Carry a second `V x V` matrix alongside the distances that records the next hop (or the last intermediate vertex) on the current best route for each pair. Whenever a distance improves through waypoint `k`, copy the corresponding routing entry. Reconstruction then walks that matrix hop by hop from `i` toward `j`. It costs another O(V^2) space and no extra asymptotic time.
- Why does the running time not depend on the number of edges?The algorithm never iterates over an edge list. Edges enter only during initialisation, when each one writes a weight into the matrix; after that every step reads and writes matrix cells. Three loops of length `V` therefore run `V^3` times whether the graph is a sparse chain or complete. That independence is exactly what makes it a poor fit for sparse graphs and a good fit for dense ones.
- What is stored on the diagonal of the finished matrix, and what should it be?`D[i][i]` is the cheapest cost of a route that leaves `i` and returns to it, and it should be `0` on any graph where shortest paths are well defined. A value below zero means a cycle of negative total weight is reachable from `i`, in which case no shortest path exists for the pairs it touches — the distances involving that cycle are not meaningful numbers.
It is a printed distance table in the back of a road atlas: expensive to typeset once, then every city-to-city lookup is instant.
saying these in an interview costs you the question
- Describes it as single-source, like a queue-driven search
- Says O(V^2) time because there is one matrix
- Claims the cost depends on the edge count
- Thinks the matrix contains routes rather than costs
- Assumes the diagonal is unused or arbitrary