# $k$-Link Shortest Path - Shortest path of length $k$ - A shortest $i$-link path must be extended from a shortest $(i-1)$-link path $ \text{path}_i(v) = \min\begin{cases} \text{path}_{i-1}(a) + w(a, v) \\ \text{path}_{i-1}(b) + w(b, v) \\ \dots & \end{cases} $ $ \text{path}_0(v) = \begin{cases} 0, & s = v \\ \infty, & s \ne v \end{cases} $ - Rows for different $k$ values, columns for each vertex - $O(kV)$ space, $O(k(V + E))$ time. - To reconstruct the path, keep track of the pointers.