最短路径算法：Floyd-Warshall算法

Floyd-Warshall算法是一种用于计算加权图中所有顶点对之间最短路径的动态规划算法。与Dijkstra算法（计算单源最短路径）或Bellman-Ford算法不同，Floyd-Warshall算法能够处理包含负权边的图（但不能处理包含负权环的图），并一次性找出所有顶点之间的最短距离。

核心思想与动态规划状态定义

算法的核心思想是：对于图中的任意两个顶点i和j，考虑所有其他顶点作为潜在的“中转站”。我们逐步尝试，是否通过引入某个中间顶点k，能够使得从i到j的路径变得更短。

我们定义一个二维数组dist作为我们的动态规划状态：

• dist[k][i][j] 表示：在考虑了前k个顶点（编号为0, 1, ..., k-1）作为中间顶点的情况下，从顶点i到顶点j的最短路径距离。

然而，通过观察可以发现，状态dist[k]只依赖于状态dist[k-1]，因此我们可以将三维数组“压平”成一个二维数组，通过覆盖来节省空间。我们最终使用一个二维数组dist[i][j]，并在算法过程中不断更新它。其含义演变为：在当前阶段，从顶点i到顶点j的已知最短距离。

算法步骤详解

假设图有n个顶点（编号从0到n-1），并用一个n×n的矩阵graph表示图的邻接矩阵。graph[i][j]表示从顶点i到顶点j的边的权重。如果i和j之间没有直接相连的边，则用无穷大（∞）表示。

步骤1：初始化
创建距离矩阵dist，其大小也是n×n。直接将图的邻接矩阵复制给dist作为初始状态。

• 对于每个顶点对(i, j)：
  • 如果i等于j，那么从自己到自己的距离dist[i][j] = 0。
  • 否则，dist[i][j] = graph[i][j]（即边的权重，如果没有直接边则为∞）。

这个初始状态dist[i][j]表示的是：不允许经过任何中间顶点时，从i到j的最短路径（也就是直接走边，或者不存在直接边）。

步骤2：动态规划核心迭代
现在，我们开始逐步允许将每个顶点作为中间顶点。我们进行n次循环，k从0循环到n-1。在每一轮循环k中，我们考虑将顶点k加入允许使用的中间顶点集合。

对于每一对顶点(i, j)，我们都要思考一个问题：“现在允许经过顶点k了，从i到j的路径会不会因为经过k而变得更短？”

具体更新规则如下：
对于所有的顶点对(i, j)，检查：
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

这个公式的含义是：

• dist[i][j]：当前已知的（允许使用前k-1个顶点作为中间顶点时）从i到j的最短距离。
• dist[i][k]：从i到k的最短距离，这个距离是在之前的状态下计算出来的，并且只使用了前k-1个中间顶点。
• dist[k][j]：从k到j的最短距离，同样只使用了前k-1个中间顶点。
• dist[i][k] + dist[k][j]：这条路径表示从i出发，先走到k，再从k走到j。这条路径是允许使用顶点k作为中间顶点的。

我们比较“不经过k的当前最短路径”和“经过k的新路径”哪个更短，然后更新dist[i][j]为更小的那个值。

重要细节：在计算dist[i][k]和dist[k][j]时，由于k是当前正在考虑的中间顶点，我们使用的是上一轮（k-1阶段）计算出的值，这保证了我们不会出现一条路径多次经过同一个顶点k的情况，符合动态规划的“无后效性”。

步骤3：迭代完成
当k从0到n-1全部迭代完成后，矩阵dist中的dist[i][j]值就是从顶点i到顶点j的真正最短路径距离。因为此时我们已经考虑了图中所有n个顶点都有可能作为中间顶点。

算法演示（一个简单例子）

考虑一个包含3个顶点的图（顶点0, 1, 2），其邻接矩阵如下（∞表示无直接边）：

初始graph:
   0   1   2
0  0   3  ∞
1  ∞   0   1
2  2   ∞   0

1. 初始化dist矩阵：直接复制graph。

   k = -1 (初始状态，不允许任何中间顶点)
   dist:
       0   1   2
   0   0   3   ∞
   1   ∞   0   1
   2   2   ∞   0
   

2. 第一轮迭代 (k=0)：允许使用顶点0作为中间顶点。
   检查所有(i, j)对：

   • (1,2): dist[1][2] = min(∞, dist[1][0] + dist[0][2]) = min(∞, ∞ + ∞) = ∞ -> 不变。
   • (2,1): dist[2][1] = min(∞, dist[2][0] + dist[0][1]) = min(∞, 2 + 3) = 5 -> 更新为5！
     更新后dist矩阵：

   k = 0 (允许中间顶点0)
   dist:
       0   1   2
   0   0   3   ∞
   1   ∞   0   1
   2   2   5   0
   

   现在我们知道，从2到1可以经过0，距离为5，比之前的∞（无直接路径）要短。

3. 第二轮迭代 (k=1)：允许使用顶点0和1作为中间顶点。
   检查所有(i, j)对：

   • (0,2): dist[0][2] = min(∞, dist[0][1] + dist[1][2]) = min(∞, 3 + 1) = 4 -> 更新为4！
   • (2,0): dist[2][0] = min(2, dist[2][1] + dist[1][0]) = min(2, 5 + ∞) = 2 -> 不变。
   • (2,2): dist[2][2] = min(0, dist[2][1] + dist[1][2]) = min(0, 5+1)=0 -> 不变。
     更新后dist矩阵：

   k = 1 (允许中间顶点0,1)
   dist:
       0   1   2
   0   0   3   4
   1   ∞   0   1
   2   2   5   0
   

   现在我们知道，从0到2可以经过1，距离为4。

4. 第三轮迭代 (k=2)：允许使用所有顶点(0,1,2)作为中间顶点。
   检查所有(i, j)对：

   • (0,0): dist[0][0] = min(0, dist[0][2] + dist[2][0]) = min(0, 4+2)=0 -> 不变。
   • (0,1): dist[0][1] = min(3, dist[0][2] + dist[2][1]) = min(3, 4+5)=3 -> 不变。
   • (1,0): dist[1][0] = min(∞, dist[1][2] + dist[2][0]) = min(∞, 1+2)=3 -> 更新为3！
   • (1,1): dist[1][1] = min(0, dist[1][2] + dist[2][1]) = min(0, 1+5)=0 -> 不变。
     更新后dist矩阵（最终结果）：

   k = 2 (允许所有中间顶点)
   dist:
       0   1   2
   0   0   3   4
   1   3   0   1
   2   2   5   0
   

最终，dist矩阵就包含了所有顶点对之间的最短路径距离。

时间复杂度与空间复杂度

• 时间复杂度：O(n³)。因为有三层嵌套循环，分别遍历k、i、j，每次循环n次。
• 空间复杂度：O(n²)。只需要存储一个n×n的距离矩阵。

算法特性与注意事项

• 负权边：Floyd-Warshall算法可以处理带有负权边的图。
• 负权环：算法不能处理包含负权环的图。因为负权环意味着可以无限绕环走，使得路径长度变为负无穷。可以通过检查最终矩阵的主对角线来判断：如果存在dist[i][i] < 0，则说明图中存在从i出发又回到i的负权环。
• 路径重建：如果需要输出具体的最短路径而不仅仅是距离，可以维护一个next矩阵，记录节点i到j的路径上i的后继节点。在更新dist[i][j]时，如果发现了更短的路径，同时更新next[i][j] = next[i][k]。