Floyd-Warshall算法求解所有顶点对最短路径

题目描述
给定一个带权有向图，图中可能包含负权边，但不存在负权环（即环上各边权值之和为负数的环）。要求计算图中任意两个顶点之间的最短路径长度。例如，在一个有n个顶点的图中，我们需要找出从顶点i到顶点j的最短路径，其中i和j的取值范围都是1到n。

关键概念

1. 所有顶点对最短路径：需要计算图中每一对顶点之间的最短距离。
2. 负权边允许存在，但图中不能有负权环（因为负权环会导致路径长度可以无限减小）。
3. 动态规划思想：通过逐步优化中间顶点的选择来更新最短路径估计。

算法核心思路
Floyd-Warshall算法使用动态规划，定义dist[k][i][j]表示从顶点i到顶点j，且中间顶点（除i和j外）的编号不超过k的所有路径中的最小权值。通过逐步增加k的值（从0到n-1），我们能够考虑更多的顶点作为中间顶点，从而逐步优化最短路径估计。

详细步骤

1. 初始化距离矩阵

   • 创建一个n×n的矩阵dist，其中dist[i][j]表示从顶点i到顶点j的直接边权值。
   • 如果i等于j，则dist[i][j] = 0（顶点到自身的距离为0）。
   • 如果存在从i到j的边，则dist[i][j]为该边的权值。
   • 如果不存在从i到j的边，则dist[i][j] = ∞（表示不可达）。

2. 动态规划迭代
   对于每个中间顶点k（从0到n-1），更新所有顶点对(i, j)的距离：

   • 状态转移方程：
     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
   • 含义：比较当前从i到j的路径是否可以通过顶点k进行优化。即，如果从i到k再到j的路径比当前记录的最短路径更短，则更新dist[i][j]。

3. 负权环检测

   • 在算法执行完毕后，检查矩阵的主对角线元素（即dist[i][i]）。
   • 如果存在某个dist[i][i] < 0，则说明图中存在负权环（因为顶点到自身的最短路径应为0，负数表示存在负权环）。

示例演示
假设有一个3个顶点的图，边权值如下：

• 边(0,1)权值为4
• 边(0,2)权值为-2
• 边(1,2)权值为3
• 边(2,1)权值为1

初始化距离矩阵：

dist = [
  [0, 4, -2],
  [∞, 0, 3],
  [∞, 1, 0]
]

迭代过程：

• k=0（考虑顶点0作为中间顶点）：
  更新dist[1][2]：min(3, dist[1][0]+dist[0][2]=∞+(-2)=∞) → 不变
  更新dist[2][1]：min(1, dist[2][0]+dist[0][1]=∞+4=∞) → 不变
  其他值无需更新。

• k=1（考虑顶点1作为中间顶点）：
  更新dist[0][2]：min(-2, dist[0][1]+dist[1][2]=4+3=7) → -2（不变）
  更新dist[2][0]：min(∞, dist[2][1]+dist[1][0]=1+∞=∞) → 不变。

• k=2（考虑顶点2作为中间顶点）：
  更新dist[0][1]：min(4, dist[0][2]+dist[2][1]=-2+1=-1) → -1
  更新dist[1][0]：min(∞, dist[1][2]+dist[2][0]=3+∞=∞) → 不变。

最终距离矩阵：

[
  [0, -1, -2],
  [∞, 0, 3],
  [∞, 1, 0]
]

所有dist[i][i]均为0，无负权环。

算法特点

• 时间复杂度：O(n³)，适用于顶点数不超过几百的图。
• 空间复杂度：O(n²)，可通过覆盖原矩阵优化空间。
• 优点：代码简洁，能处理负权边，适合稠密图。
• 缺点：对于稀疏图效率低于多次运行Dijkstra算法。