What is the Floyd-Warshall Algorithm?
Understand how Floyd-Warshall computes all-pairs shortest paths in O(V^3) time, with mechanism, code, and a full interview answer.
Expected Interview Answer
Floyd-Warshall is a dynamic programming algorithm that computes the shortest path between every pair of vertices in a weighted graph in O(V^3) time by progressively allowing each vertex, in turn, to act as an intermediate point on paths between all other pairs.
The algorithm maintains a V-by-V distance matrix initialized with direct edge weights (infinity where no edge exists, zero on the diagonal), then loops over every vertex k as a potential intermediate, and for every pair (i, j) checks whether routing through k — dist[i][k] + dist[k][j] — beats the currently known dist[i][j]. After considering all V vertices as possible waypoints, the matrix holds the true shortest distance between every pair. This all-pairs approach in O(V^3) time and O(V^2) space is simpler to implement than running Dijkstra or Bellman-Ford from every vertex individually, and it naturally handles negative edge weights, only failing when a negative cycle exists (visible as a negative value on the diagonal). It is the standard choice for dense graphs or when all-pairs distances are genuinely needed, such as network diameter calculations or transitive closure.
- Computes shortest paths between all pairs of vertices at once
- Simple triple-nested-loop implementation
- Handles negative edge weights (not negative cycles)
- Naturally extends to transitive closure and path reconstruction
AI Mentor Explanation
A tournament logistics team wants the cheapest travel cost between every pair of host cities, so they consider each city, one at a time, as a possible layover between every other pair of cities. For city k as the candidate layover, they check every pair (i, j) and ask whether flying i to k to j beats the currently known best cost from i to j. After cycling through every city as a candidate layover, the full grid of city-to-city costs is guaranteed optimal, since every possible intermediate stop has been considered. This grid-filling approach answers 'cheapest route between any two grounds' for the whole tournament in one pass, rather than solving each pair separately.
Step-by-Step Explanation
Step 1
Initialize the distance matrix
dist[i][j] = edge weight if an edge exists, 0 on the diagonal, infinity otherwise.
Step 2
Loop over every vertex k as intermediate
For k from 1 to V, consider k as a possible waypoint on paths between all pairs.
Step 3
Relax every pair through k
For every (i, j), set dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Step 4
Read off all-pairs shortest paths
After all k are processed, dist[i][j] holds the true shortest distance between every pair.
What Interviewer Expects
- State O(V^3) time and O(V^2) space complexity
- Explain the triple loop and why k must be the outermost loop
- Contrast with running Dijkstra/Bellman-Ford from every source (all-pairs vs single-source)
- Note it detects negative cycles via a negative value on the diagonal
Common Mistakes
- Putting the k loop innermost instead of outermost, which breaks correctness
- Claiming it handles negative cycles correctly instead of just detecting them
- Forgetting the O(V^3) cost makes it unsuitable for very large sparse graphs
- Confusing it with Bellman-Ford, which is single-source, not all-pairs
Best Answer (HR Friendly)
“Floyd-Warshall computes the shortest distance between every pair of points in a graph, all at once, by checking whether routing through each possible waypoint improves any pair's known distance. I reach for it when I need a complete distance table between all points rather than just paths from one starting point, and it is simple to implement despite being O(V^3).”
Code Example
def floyd_warshall(vertices, edges):
dist = {i: {j: float("inf") for j in vertices} for i in vertices}
for v in vertices:
dist[v][v] = 0
for u, v, weight in edges:
dist[u][v] = min(dist[u][v], weight)
for k in vertices:
for i in vertices:
for j in vertices:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distFollow-up Questions
- How would you reconstruct the actual path between two vertices, not just the distance?
- How would you detect a negative cycle using the resulting distance matrix?
- When would running Dijkstra from every vertex be more efficient than Floyd-Warshall?
- How would you compute the transitive closure of a graph using this same structure?
MCQ Practice
1. What is the time complexity of the Floyd-Warshall algorithm on a graph with V vertices?
Three nested loops over all V vertices give O(V^3) time.
2. In Floyd-Warshall, what does the outer loop variable k represent?
k is tried as a possible intermediate waypoint for every pair (i, j) in that iteration.
3. How can you tell a graph has a negative-weight cycle from the final Floyd-Warshall matrix?
A negative value on the diagonal means a vertex has a negative-cost path back to itself, indicating a negative cycle.
Flash Cards
What problem does Floyd-Warshall solve? — Shortest paths between every pair of vertices in a weighted graph.
What is Floyd-Warshall's time complexity? — O(V^3), from three nested loops over all vertices.
Why must the k loop be outermost? — Because dist[i][j] must be fully updated for intermediate vertices 1..k-1 before k itself is used as an intermediate.
How does Floyd-Warshall detect a negative cycle? — A negative value appears on the diagonal (dist[v][v] < 0) after the algorithm runs.