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

题目描述
给定一个带权有向图（或无向图），图中可能包含负权边，但不允许存在负权环。要求计算图中任意两个顶点之间的最短路径距离。具体来说，需要生成一个距离矩阵，其中每个元素dist[i][j]表示从顶点i到顶点j的最短路径长度。

解题过程

1. 问题分析

   • 与单源最短路径算法（如Dijkstra、Bellman-Ford）不同，Floyd-Warshall算法直接解决所有顶点对的最短路径问题。
   • 核心思想是动态规划：逐步考虑图中所有顶点作为中间顶点，更新每对顶点之间的最短距离。
   • 适用于稠密图（边数接近顶点数平方），因为其时间复杂度为O(n³)，与边数无关。

2. 算法准备

   • 输入：图的邻接矩阵graph，其中graph[i][j]表示边(i→j)的权重。若两点无直接边，初始值为无穷大（∞）；对角线graph[i][i]初始化为0。
   • 输出：距离矩阵dist，其中dist[i][j]为最终的最短距离。
   • 关键思路：设dist[k][i][j]表示从i到j且中间顶点编号不超过k的最短路径长度。通过优化可降为二维数组。

3. 动态规划状态转移

   • 定义状态：dist[k][i][j]表示考虑前k个顶点作为中间顶点时，i到j的最短距离。
   • 状态转移方程：

\[ dist[k][i][j] = \min(dist[k-1][i][j],\ dist[k-1][i][k] + dist[k-1][k][j]) \]

 - 第一项：不经过顶点k，保持之前的最短距离。
 - 第二项：经过顶点k，路径分解为i→k和k→j两部分。

• 优化：可省略k的维度，直接在原矩阵上更新，即：

\[ dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j]) \]

4. 算法步骤

   • 步骤1：初始化距离矩阵dist，直接复制邻接矩阵graph。
   • 步骤2：三重循环遍历：
     • 外层循环k从0到n-1：依次考虑每个顶点作为中间顶点。
     • 内层双重循环i、j：对每对顶点(i,j)，检查是否通过顶点k能缩短距离。
   • 步骤3：检查负权环：遍历对角线元素dist[i][i]，若存在负数说明有负权环。

5. 示例演示
   考虑图的邻接矩阵（无直接边设为∞）：

   graph = [
     [0, 3, ∞, 7],
     [8, 0, 2, ∞],
     [5, ∞, 0, 1],
     [2, ∞, ∞, 0]
   ]
   

   • k=0（经过顶点0）：
     更新dist[2][1] = min(∞, 5+3)=8, dist[2][3]=min(1,5+7)=1（不变）等。
   • k=1（经过顶点1）：
     更新dist[0][2]=min(∞,3+2)=5, dist[2][0]=min(5,8+8)=5（不变）等。
   • 继续k=2,3，最终矩阵为：

     [
       [0, 3, 5, 6],
       [5, 0, 2, 3],
       [5, 8, 0, 1],
       [2, 5, 7, 0]
     ]
     

6. 关键点说明

   • 顺序重要性：外层k循环必须按顶点编号顺序，确保动态规划状态正确转移。
   • 负权边处理：允许存在负权边，但需在结束后检查负权环（对角线负值）。
   • 路径重建：可额外维护next矩阵记录路径下一顶点，通过回溯还原完整路径。

7. 复杂度分析

   • 时间复杂度：O(n³)，因三重循环遍历所有顶点组合。
   • 空间复杂度：O(n²)，仅需存储距离矩阵。

通过以上步骤，Floyd-Warshall算法系统地计算出所有顶点对的最短距离，兼顾代码简洁性与功能全面性。