Table update

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Table update

In each k step, all (i, j) pairs are visited and the formula dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) is applied.

This updates the distance if a shorter path using k as a stopover is found. When all k values are done, the matrix is complete.

Algorithm end

When all k values are processed, the dist matrix contains the shortest distances for all pairs. No more updates occur.

The final matrix is the original graph solved for all pairs. Even for a single query, the whole matrix is computed.

Exercise floyd_warshall function

Write floyd_warshall(graph). Update the dist matrix with a triple loop, return it. Print the final matrix with print(floyd_warshall(init_graph())).

Show example solution

def init_graph():
    # Return adjacency matrix
    return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
def floyd_warshall(graph):
    # Find all-pairs shortest paths
    n = len(graph)
    dist = [row[:] for row in graph]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
print(floyd_warshall(init_graph()))

Test yourself

Table update: match the terms

dist[i][j]

Current
dist[i][k]

i→k
dist[k][j]

k→j
min

Smallest
What is the shortest distance from 0 to 3?
- 7
- 4
- 6
- 999
Show answer

6 — Path 0→1→2→3 gives 3+1+2=6.

Inner update

dist[i][j] = ____(dist[i][j], dist[i][k] + dist[k][j])

Show answer

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Next lesson: Summary - Floyd-Warshall

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies