Floyd-Warshall: All-Pairs Shortest Paths
Fill the all-pairs distance matrix using the three-nested-loop Floyd-Warshall algorithm and apply it to find the smallest number of hops between all node pairs.
Floyd-Warshall: All-Pairs Shortest Paths is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
All-Pairs Shortest Paths
Floyd-Warshall computes shortest paths between every pair of nodes in a weighted graph — including graphs with negative edge weights (but not negative cycles). Running Dijkstra from each source takes O(V × (V+E) log V); Floyd-Warshall runs in O(V³) regardless of edge density. For dense graphs with V ≤ 500, Floyd-Warshall is often simpler and comparably fast.
The Core Idea: Intermediate Nodes
Floyd-Warshall's insight: dp[i][j][k] = shortest path from i to j using only nodes {0, 1, ..., k} as intermediates. Either the shortest path uses node k as an intermediate, or it doesn't. If it does: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. If not: dp[i][j][k] = dp[i][j][k-1]. Since the third dimension only progresses forward, it can be eliminated — we update in-place.
Initialisation of the Distance Matrix
Start with a V×V matrix: dist[i][i] = 0 (zero self-distance), dist[i][j] = weight for direct edges, and dist[i][j] = inf for non-edges. Then iterate over all intermediate nodes k, updating pairs (i, j). The outer loop over k must come first so we correctly build up paths through an increasing set of allowed intermediates.
def floyd_warshall(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w # directed graph
for k in range(V): # intermediate node
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distComplete Implementation with Example
Let's trace Floyd-Warshall on a 4-node graph. After processing each intermediate node k, the matrix fills in with shorter paths that route through node k. The algorithm naturally handles multiple hops by building shortest paths incrementally.
def floyd_warshall(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] != INF and dist[k][j] != INF:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
print([x if x != float('inf') else 'INF' for x in row])Detecting Negative Cycles
After running Floyd-Warshall, check the main diagonal: if any dist[i][i] < 0, there is a negative cycle passing through node i. This is because a negative cycle allows reaching i from i with negative cost. If no negative cycle exists, all diagonal entries remain 0.
def has_negative_cycle_fw(V, edges):
dist = floyd_warshall(V, edges)
for i in range(V):
if dist[i][i] < 0:
return True # negative cycle through node i
return False
# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg)) # TruePath Reconstruction
To reconstruct the actual path from i to j, maintain a next[i][j] matrix: initially next[i][j] = j for direct edges. When updating via intermediate k, set next[i][j] = next[i][k]. To recover the path: start at i, follow next pointers until j is reached. This adds O(V²) space and O(V) per path reconstruction.
def fw_with_path(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
nxt = [[None]*V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w; nxt[u][v] = v
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
nxt[i][j] = nxt[i][k]
return dist, nxt
def get_path(nxt, i, j):
if nxt[i][j] is None: return []
path = [i]
while i != j:
i = nxt[i][j]; path.append(i)
return pathTransitive Closure
A simpler variant: Transitive Closure answers 'is node j reachable from node i?' for all pairs. Replace distances with booleans: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). This is Floyd-Warshall with boolean OR instead of addition and min. Initialise reach[i][i] = True and reach[i][j] = True for direct edges.
def transitive_closure(V, edges):
reach = [[False]*V for _ in range(V)]
for i in range(V):
reach[i][i] = True
for u, v, _ in edges:
reach[u][v] = True
for k in range(V):
for i in range(V):
for j in range(V):
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
return reach
edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2]) # True (0 can reach 2 via 0->1->2)Complexity and When to Use
Floyd-Warshall: O(V³) time, O(V²) space. For dense graphs (E ≈ V²) with V ≤ 300, this is faster than running Dijkstra V times (also O(V³) in that case). For sparse graphs with V = 1000 and E = 3000, V Dijkstras cost O(V×E×log V) ≈ 33M while Floyd-Warshall costs O(V³) = 10⁹ — Dijkstra wins. Know when each is appropriate.
Minimum Number of Hops Between All Pairs
Set all edge weights to 1 (or use a boolean adjacency matrix with Floyd-Warshall using addition instead of min): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). This computes the minimum number of hops between all pairs — an all-pairs BFS result but computed with a single O(V³) Floyd-Warshall pass.
def min_hops_all_pairs(V, adj_list):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for j in adj_list[i]:
dist[i][j] = 1
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0]) # [0, 1, 1, 2, INF]Interview Context: When Interviewers Ask About Floyd-Warshall
Floyd-Warshall appears in interviews on questions involving: (1) all-pairs distances on a small graph, (2) finding if any cycle exists with negative total weight, (3) computing shortest paths in constraint propagation problems, and (4) problems explicitly asking for O(V³) solutions where V ≤ 200. Always mention the three-loop structure and the requirement of no negative cycles for correctness.
Undirected Graphs with Floyd-Warshall
For undirected graphs, add both directions for each edge: dist[u][v] = dist[v][u] = weight. The rest of the algorithm is identical. The resulting matrix is symmetric: dist[i][j] == dist[j][i] for all pairs. When initialising, be careful not to accidentally assign directional edges — undirected edges must be added in both directions to the initial matrix before running the three loops.
def fw_undirected(V, edges):
INF = float('inf')
dist = [[INF]*V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
dist[v][u] = w # both directions for undirected
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Floyd-Warshall computes all-pairs shortest paths with three nested loops and the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), negative cycles are detectable by checking if any dist[i][i] < 0 after completion, and the algorithm runs in O(V³) time and O(V²) space. Next up we revisit shortest-path applications with Network Delay Time and path reconstruction techniques.
Frequently asked questions
Is the “Floyd-Warshall: All-Pairs Shortest Paths” lesson free?
Yes — the full text of “Floyd-Warshall: All-Pairs Shortest Paths” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Floyd-Warshall: All-Pairs Shortest Paths”?
Fill the all-pairs distance matrix using the three-nested-loop Floyd-Warshall algorithm and apply it to find the smallest number of hops between all node pairs. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Floyd-Warshall: All-Pairs Shortest Paths” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction