Floyd-Warshall Algorithm Implementation
What You'll Learn
You'll learn how to implement the triple-nested loop structure that systematically updates the distance matrix to find all-pairs shortest paths.
The Core Structure
The Floyd-Warshall algorithm uses three nested loops to consider every possible intermediate vertex for every pair of source and destination vertices. Think of it like testing every possible "connector friend" when finding the shortest social distance between any two people in a network.
The outer loop iterates through each potential intermediate vertex k. For each k, the middle and inner loops examine all pairs of vertices (i, j) to see if routing through k offers a shorter path than the current known distance.
The Implementation Pattern
# dist[][] is initialized with direct edge weights
# dist[i][i] = 0 for all i
# dist[i][j] = infinity if no direct edge exists
V = number_of_vertices
for k in range(V): # intermediate vertex
for i in range(V): # source vertex
for j in range(V): # destination vertex
# Relax: check if going through k is better
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
Why This Order Matters
The order of loops is crucial: k must be the outermost loop. By processing vertices as intermediate nodes in sequence, we build up solutions incrementally—using paths through vertices {0, 1, ..., k-1} to compute paths through {0, 1, ..., k}.
The matrix is updated in place, and after the algorithm completes, dist[i][j] contains the shortest path distance from vertex i to vertex j.
Key Takeaway: Floyd-Warshall's triple-nested loop systematically considers each vertex as an intermediate step, updating the distance matrix by checking if routing through vertex k shortens any pair's path.