Sign in to watch this lesson
Advanced - Graphs · 4:07
Paths of Fixed Length (Matrix Power, Min-Plus)
The k-th power of a graph's adjacency matrix counts the walks with exactly k edges between every pair of vertices, and binary exponentiation computes it in O(n³ log k). Swapping (+, ×) for (min, +) turns the same code into the cheapest walk with exactly k edges, which is the matrix form of Bellman–Ford. Giving every vertex a twin with a loop turns 'exactly k + 1 edges' into 'at most k edges'.
You will learn
- Explain why (G^k)[i][j] counts the walks with exactly k edges from i to j (multi-edges as counts, loops allowed), and that these are walks, not simple paths
- Raise an n × n matrix to a power k ≤ 10^18 with binary exponentiation in O(n³ log k), reducing modulo p without overflow, and estimate when n is too large
- Use the min-plus product with the correct identity (0 on the diagonal, ∞ elsewhere) and an ∞ guard to find the cheapest walk with exactly k edges
- Turn 'exactly k' into 'at most k' with the vertex-twin trick, and relate k min-plus steps to k phases of Bellman–Ford