什么是 Floyd-Warshall 算法？

Floyd-Warshall 算法（简称 Floyd 算法）是一种用于计算 所有顶点对之间最短路径 的算法。与 Dijkstra 和 SPFA 不同，它不是单源最短路算法，而是一次性计算出图中任意两点之间的最短距离。

Floyd 算法可以正确处理带有 负权边 的图，但不能处理带有 负环 的图。它非常适合用于稠密图。

核心思想：动态规划

Floyd 算法的本质是一个动态规划。我们定义一个二维数组 dp[k][i][j]，表示从顶点 i 到顶点 j，只允许经过编号从 1 到 k 的顶点作为中间点时，所能得到的最短路径长度。