Floyd Warshall All Pairs Shortest Path Flashcards
Term
Definition
All-Pairs Shortest Path (APSP)
Find the shortest path between every pair of vertices in a graph. If there are n vertices, compute n^2 shortest paths.
Distance Matrix D
A matrix where D[i][j] stores the shortest path distance from vertex i to vertex j.
Next Matrix N
A matrix where N[i][j] stores the next vertex to visit on the shortest path from i to j.
APSP using Dijkstra
Run Dijkstra’s algorithm from every vertex (only works with non-negative edge weights). Time complexity: O(V(E + V log V)).
APSP using Bellman-Ford
Run Bellman-Ford from every vertex. Handles negative weights. Time complexity: O(V^2E).
Floyd-Warshall Algorithm
Dynamic programming algorithm that computes shortest paths between all pairs. Time complexity: O(V^3).
Floyd-Warshall D_k[i][j]
Shortest path from i to j using only intermediate nodes ≤ k.
Floyd-Warshall Base Case D_0
D_0[i][j] = weight(i,j) if edge exists; 0 if i==j; ∞ otherwise.
Floyd-Warshall Recurrence
D_k[i][j] = min(D_{k-1}[i][j], D_{k-1}[i][k] + D_{k-1}[k][j]).
Floyd-Warshall Next Matrix Update
If D_k[i][j] updated via path through k, then N[i][j] = N[i][k]; otherwise, N[i][j] = N[i][j].
Matrix Multiplication Method
D^k[i][j] = shortest path from i to j with ≤ k edges. Built using min-plus matrix multiplication.
Min-Plus Matrix Multiplication
Special multiplication: replace addition with min, and multiplication with +.
Repeated Squaring
Efficiently compute D^n via powers of 2: D^1, D^2 = D^1D^1, D^4 = D^2D^2, etc. Time: O(n^3 log n).
Transitive Closure
Graph with edges (i,j) if there is a path from i to j. Can be computed using APSP with boolean logic.
Transitive Closure via Boolean Matrix
Replace shortest path weights with True/False. Use AND and OR instead of min and +.
