Table update
- Algorithms course
- Advanced
- Lesson 27/56
- 4 min
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.
Practice 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())).
Starter code
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 pathsSample 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()))Expected output
[[0, 3, 4, 6], [999, 0, 1, 3], [999, 6, 0, 2], [999, 4, 5, 0]]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Table update: match the terms
| Term | Meaning |
|---|---|
dist[i][j] |
Current |
dist[i][k] |
i→k |
dist[k][j] |
k→j |
min |
Smallest |
2 What is the shortest distance from 0 to 3?
- 7
- 4
- 6 Correct answer
- 999
Explanation: Path 0→1→2→3 gives 3+1+2=6.
3 Inner update
dist[i][j] = ____(dist[i][j], dist[i][k] + dist[k][j])dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Explanation: min is right.