Floyd-Warshall algorithm
Shortest paths between every pair of vertices: the distance matrix, step k, the update formula, loop order, the successor matrix, the O(n³) cost and choosing the right shortest-path algorithm.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Intermediate vertex: what is it?
Show the answer
A vertex that a path goes through between its start and its end; step k of the algorithm allows vertex k to play that role.
After step k, d[i][j] is the shortest length of a path from i to j whose intermediates are all among vertices 1 to k. At step n, all vertices are allowed.
The arcs are 0 → 3, 3 → 2 and 2 → 1, each of weight 1. The code puts the loop on k inside. What does it print for row 0?
```python
INF = float("inf")
d = [[0, INF, INF, 1], [INF, 0, INF, INF], [INF, 1, 0, INF], [INF, INF, 1, 0]]
n = 4
for i in range(n):
for j in range(n):
for k in range(n):
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
print(d[0])`[0, inf, 2, 1][0, 3, 2, 1][0, inf, inf, 1][0, 3, inf, 1]
Show the answer
[0, inf, 2, 1]For d[0][1], the path 0, 3, 2, 1 is needed, found with 3 then 2 as intermediates: but d[0][2] is only computed after d[0][1], which stays at inf. The correct row,
[0, 3, 2, 1], needs k outermost: each step is then complete for all cells before the next.At step k of Floyd-Warshall, set d[i][j] = …(d[i][j], d[i][k] … d[k][j]) for each pair (i, j).
Show the answer
At step k of Floyd-Warshall, set d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for each pair (i, j).
The best known path is compared with the one going through k: from i to k, then from k to j. For Warshall's transitive closure, min and + become or and and.
Distance matrix: what is it?
Show the answer
A square table whose cell (i, j) holds the length of the best known path from vertex i to vertex j: 0 on the diagonal, infinity when no path is known.
At the start it holds the arc weights. Floyd-Warshall fills it in n steps; it keeps only lengths, and the paths are read back with the successor matrix.