$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{array}{ll}{\text{path}}_{i-1}(a)+w(a,v)& \\ {\text{path}}_{i-1}(b)+w(b,v)& \\ \dots & \end{array}$$ $${\text{path}}_0(v)=\{\begin{array}{ll}0,& s=v\\ \infty ,& s\ne v\end{array}$$

• 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.