xxx Floyd-Warshall算法求解所有顶点对最短路径 题目描述 给定一个带权有向图，图中可能包含负权边但不包含负权环。要求计算图中任意两个顶点之间的最短路径长度。具体来说，给定图G=(V,E)和边权函数w: E→R，我们需要计算一个|V|×|V|的矩阵D，其中D[ i][ j ]表示从顶点i到顶点j的最短路径距离。 解题过程详解 1. 问题分析 单源最短路径算法（如Dijkstra、Bellman-Ford）只能计算从一个顶点到其他所有顶点的最短路径 要计算所有顶点对之间的最短路径，需要运行|V|次单源最短路径算法 Floyd-Warshall算法提供了一种更直接的方法，通过动态规划一次性解决所有顶点对的最短路径问题 2. 算法核心思想 Floyd-Warshall算法基于以下观察：考虑从顶点i到顶点j的路径，如果允许路径经过顶点集合{1,2,...,k}，那么最短路径有两种可能： 不经过顶点k：路径只允许经过顶点{1,2,...,k-1} 经过顶点k：路径由i→k和k→j两段组成，每段都只允许经过顶点{1,2,...,k-1} 3. 动态规划定义 定义dp[ k][ i][ j ]为从顶点i到顶点j，且中间顶点只允许来自集合{1,2,...,k}的最短路径长度。 状态转移方程： dp[ k][ i][ j] = min(dp[ k-1][ i][ j], dp[ k-1][ i][ k] + dp[ k-1][ k][ j ]) 4. 空间优化 由于dp[ k]只依赖于dp[ k-1 ]，我们可以使用二维数组进行空间优化： 设dist[ i][ j ]表示当前计算的最短路径距离 5. 算法步骤 步骤1：初始化距离矩阵 如果i=j，dist[ i][ j ] = 0 如果存在边i→j，dist[ i][ j ] = w(i,j) 否则，dist[ i][ j ] = ∞ 步骤2：三重循环更新距离矩阵 对于k从1到|V|： 对于i从1到|V|： 对于j从1到|V|： 如果dist[ i][ k] + dist[ k][ j] < dist[ i][ j ]： dist[ i][ j] = dist[ i][ k] + dist[ k][ j ] 步骤3：检查负权环（可选） 如果存在dist[ i][ i] < 0，说明图中存在负权环 6. 算法正确性证明 基础情况：当k=0时，dist矩阵包含所有直接边的权重 归纳假设：假设dist[ i][ j ]包含经过顶点{1,2,...,k-1}的最短路径 归纳步骤：当考虑顶点k时，我们正确更新了经过顶点{1,2,...,k}的最短路径 7. 时间复杂度分析 三重循环，每层循环|V|次 总时间复杂度：O(|V|³) 空间复杂度：O(|V|²) 8. 路径重建（可选扩展） 要重建具体的最短路径，可以维护前驱矩阵next： 初始化：如果存在边i→j，next[ i][ j] = j；否则next[ i][ j ] = null 更新：当dist[ i][ j] > dist[ i][ k] + dist[ k][ j]时，next[ i][ j] = next[ i][ k ] 重建路径：从i开始，沿着next指针直到到达j 9. 算法特点 优点：代码简单，容易实现；能处理负权边；能检测负权环 缺点：时间复杂度较高，不适合大规模图 适用场景：稠密图；需要计算所有顶点对最短路径；图中包含负权边 这个算法通过动态规划的思想，系统地考虑了所有可能的中间顶点，确保最终得到所有顶点对之间的最短路径距离。