Floyd–Warshall Algorithm: Coding Interview Guide

TL;DR: The Floyd–Warshall algorithm computes all-pairs shortest paths with dynamic programming. Initialize a distance matrix from the graph, then for every intermediate vertex k update each pair with dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). It runs in O(V³) time and O(V²) space and can expose negative cycles through negative diagonal entries.

What is the Floyd–Warshall algorithm?

Floyd–Warshall is a dynamic programming algorithm for shortest paths between every ordered pair of vertices. It works with directed or undirected weighted graphs and permits negative edges. If a relevant negative-weight cycle exists, however, some shortest paths have no finite minimum because repeatedly traversing the cycle keeps reducing the path cost.

The algorithm is memorable because it turns a global path problem into one decision: for the current intermediate vertex k, is the best known path from i to j better as it is, or by going from i to k and then k to j?

How do you derive the recurrence?

Define D(k, i, j) as the shortest distance from i to j whose intermediate vertices may come only from the first k vertices. A shortest permitted path either avoids vertex k, keeping D(k−1, i, j), or uses k and splits into the best permitted path from i to k plus the best permitted path from k to j.

That gives the recurrence:

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

Because stage k depends only on stage k−1 values in a compatible way, the matrix can be updated in place. This reasoning also explains the critical loop order: k must be the outermost loop. Putting i or j outside changes the invariant and can use partially permitted paths incorrectly.

How do you initialize the distance matrix?

Create a V by V matrix. Set dist[i][i] to zero, set a direct edge’s cell to its weight, and use infinity when no direct edge exists. If parallel edges are possible, keep the smallest direct weight. Before adding two distances, verify that both are finite so an infinity sentinel does not overflow or create a false candidate.

How do you trace Floyd–Warshall in an interview?

Label the matrix rows as sources and columns as destinations. Show the initial matrix, then choose one k and evaluate representative cells. For each cell, compare the current value with the route through k. Update only when both segments are reachable and the new sum is smaller.

You normally do not need to draw every matrix for a large example. Trace enough cells to demonstrate the invariant, including one improvement and one unchanged value. State that after completing k, every matrix entry is optimal among paths whose intermediate vertices are limited to the processed set.

What pseudocode should you write?

Use three nested loops with k on the outside:

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Explain the finite checks and numeric type. In languages with a large integer sentinel, adding infinity to a negative value can look finite or overflow. A guard is part of correctness, not merely an implementation detail.

What are the time and space complexities?

The three loops examine every combination of k, i, and j, so runtime is O(V³). The distance matrix occupies O(V²) space. In-place updating avoids a three-dimensional table, while a next-hop or predecessor matrix for path reconstruction adds O(V²) more space.

Floyd–Warshall is often attractive for modest dense graphs because its implementation is compact and predictable. For a large sparse graph with nonnegative edges, running Dijkstra from each source can be more efficient. Always compare the required output, graph density, weight constraints, and vertex count before choosing.

How do you reconstruct the actual shortest path?

Distances alone do not reveal the vertex sequence. Maintain a next[i][j] matrix initialized to j when a direct edge from i to j exists. Whenever routing through k improves dist[i][j], set next[i][j] to next[i][k]. To reconstruct a path, repeatedly move from the current vertex to next[current][destination] until reaching the destination.

Check for unreachable pairs before reconstruction, and protect against negative-cycle cases. If a pair can travel to a negative cycle and then reach the destination, there is no finite shortest path to reconstruct.

How does Floyd–Warshall detect negative cycles?

After the algorithm finishes, inspect the diagonal. A value dist[v][v] < 0 proves that a negative-weight cycle is reachable from v and can return to v. This is stronger than merely finding a negative edge; negative edges can exist in graphs with perfectly valid shortest paths.

If the interviewer asks which pairs are affected, identify every i and j for which i can reach such a vertex v and v can reach j. Those pairs can loop through the negative cycle arbitrarily many times, so their shortest-path value is not finite.

When should you choose another shortest-path algorithm?

Use breadth-first search for unweighted graphs, Dijkstra for single-source problems with nonnegative weights, and Bellman–Ford for a single source when negative weights or reachable negative-cycle detection matter. Floyd–Warshall is the direct choice when all-pairs distances are required and cubic time is acceptable.

Which interview mistakes should you avoid?

Do not put k inside another loop, forget zeroes on the diagonal, add infinity without a guard, confuse negative edges with negative cycles, or claim that O(V²) matrix space includes the input automatically in every representation. Clarify whether the graph is directed, whether parallel edges exist, and whether the interviewer needs distances, paths, or cycle-affected pairs.

Practice the coding interview assistant workflow, compare the Bellman–Ford algorithm, and review the Big O complexity cheat sheet.

Frequently asked questions

Practice the invariant, not just the loops

YesToTheOffer can help structure a coding explanation, ground it in your private preparation notes, examine edge cases, and preserve the interview transcript for later review.