Floyd-Warshall's core insight: can I improve the path from to by routing through an intermediate vertex ?
If dist[i][k] + dist[k][j] < dist[i][j], then going through is better. The algorithm considers vertices one at a time as potential intermediates. After processing vertex , all paths using vertices are optimal. This builds up the solution incrementally, which is the essence of dynamic programming.