Course contentsShow
← Computer Science
Lesson 993 of 2,87223. Shortest Path AlgorithmsFree lesson

Floyd-Warshall Algorithm Implementation

Implementing the triple-nested loop structure and updating the distance matrix systematically.

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.