Define dp[k][i][j] as the shortest path from to using only vertices as intermediates. Base case: dp[0][i][j] = edge weight from to (or infinity if no edge). Transition: dp[k+1][i][j] = min(dp[k][i][j], dp[k][i][k] + dp[k][k][j]). This asks: is it better to skip vertex or route through it?
The answer determines the best path. This DP formulation is the foundation of Floyd-Warshall.