The DP State

Define dp[k][i][j] as the shortest path from $i$ to $j$ using only vertices $\{0, 1, \ldots, k-1\}$ as intermediates. Base case: dp[0][i][j] = edge weight from $i$ to $j$ (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 $k$ or route through it?

The answer determines the best path. This DP formulation is the foundation of Floyd-Warshall.