How does the Floyd-Warshall algorithm work? | Interview Question

Q: How does the Floyd-Warshall algorithm work?

**Target Audience:** Beginners preparing for coding interviews — no graph-algorithm background assumed **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Old road atlases had a mileage chart: a big table with every city down the side and across the top, and in each square the distance between the two cities. Suppose you only know the **direct** roads, so most squares are blank ("no direct road"). How do you fill in the whole chart? Here is a patient way. First, allow trips to stop over in city 1: for every pair of cities, check whether going through city 1 is shorter than what the square says, and if so, write the new number. Then allow stopovers in c

The problem

Question presented to candidate: "Explain the Floyd-Warshall algorithm. Implement it in Python for a directed weighted graph with V nodes, return the matrix of shortest distances between every pair, and tell me how you would detect a negative cycle."

What a strong answer should cover:

The DP idea: after processing k, dist[i][j] is the shortest path using only nodes 0..k as intermediates; the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
The loop order: k must be the outermost loop, and why updating one matrix in place is safe.
O(V³) time and O(V²) space; when it beats running Dijkstra from every node (small or dense graphs, negative weights).
Negative weights are fine; a negative cycle shows up as dist[i][i] < 0; a next matrix rebuilds routes.
Python specifics: float("inf") for missing edges, building the matrix with a list comprehension (not [[INF] * n] * n, which aliases rows), and pure-Python triple loops being slow for large V.

Clarifying questions expected:

"How many nodes? Are negative weights or negative cycles possible?"
"Do you need the routes, or only the distances?"

Code / implementation expected: Yes — a Python floyd_warshall(n, edges) returning the distance matrix, ideally plus a next matrix for route reconstruction.

dsa
graph
shortest-path
dynamic-programming

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no graph-algorithm background assumed Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Old road atlases had a mileage chart: a big table with every city down the side and across the top, and in each square the distance between the two cities. Suppose you only know the direct roads, so most squares are blank ("no direct road"). How do you fill in the whole chart?

Here is a patient way. First, allow trips to stop over in city 1: for every pair of cities, check whether going through cit

The solution is hidden so you can try first

12 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonAll-pairs distances and route rebuilding

Practice

PythonLoop order, negative edges and negative cycles

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.