Floyd-Warshall算法求解所有顶点对最短路径
字数 1736 2025-10-27 19:14:05

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

题目描述
给定一个带权有向图，图中可能包含负权边，但不存在负权回路。要求计算图中任意两个顶点之间的最短路径长度。也就是说，我们需要一个矩阵作为结果，其中第i行第j列的元素表示从顶点i到顶点j的最短路径的权值之和。

解题思路
我们将采用动态规划的方法来解决这个问题。核心思想是：逐步考虑将每个顶点作为中间顶点，来更新任意两点间的最短路径估计值。

  1. 状态定义
    我们定义一个二维数组 dist，其中 dist[k][i][j] 表示：在考虑前k个顶点（即顶点0, 1, ..., k-1）作为中间顶点的情况下，从顶点i到顶点j的最短路径长度。
    然而，我们可以通过重用同一个二维数组来节省空间，将状态优化为 dist[i][j]，并在算法过程中不断更新它。此时，dist[i][j] 表示当前状态下（即已经考虑过某些中间顶点后）的i到j的最短路径估计值。

  2. 初始状态（k=0）
    在没有任何中间顶点可用时，从i到j的最短路径有两种情况：

    • 如果i等于j，那么路径长度为0。
    • 如果i不等于j，那么最短路径就是连接i和j的边的权值。如果不存在直接的边，我们先用一个很大的数（比如无穷大）来表示不可达。
      因此，我们初始化距离矩阵 dist：
    • dist[i][i] = 0（顶点到自身的距离为0）
    • 对于每条边 (u, v, w)（表示从u到v有一条权值为w的边），dist[u][v] = w
    • 对于其他情况，dist[i][j] = 无穷大

  3. 状态转移方程（核心步骤）
    现在，我们开始逐个考虑将每个顶点k（从0到n-1）加入允许的中间顶点集合。
    对于每一对顶点(i, j)，我们检查是否存在一条路径，通过新加入的顶点k，能够比当前已知的路径更短。
    具体来说，对于每一对(i, j)，我们比较：

    • 不经过k的当前最短路径：dist[i][j]（即在上一步状态下的值）
    • 经过k的新路径：这条路径是从i到k，再从k到j。其长度为 dist[i][k] + dist[k][j]（注意，这里的 dist[i][k] 和 dist[k][j] 是在当前步骤中已经更新过的，意味着它们本身可能已经利用了之前加入的中间顶点，从而保证了最优子结构）。
      我们选择两者中较小的那个作为新的最短路径估计值。
      状态转移方程为：
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

  4. 算法步骤
    基于以上思路，算法的具体步骤非常清晰：
    a. 初始化距离矩阵 dist，如上所述。
    b. 循环k，从0到n-1（n为顶点总数）：
    对于每一个k，循环每一对顶点(i, j)（i和j都从0到n-1）：
    如果 dist[i][k] 和 dist[k][j] 都不是无穷大（即i到k和k到j是可达的），并且 dist[i][k] + dist[k][j] 小于当前的 dist[i][j]：
    那么更新 dist[i][j] = dist[i][k] + dist[k][j]。
    c. 循环结束后，dist 矩阵中存储的就是所有顶点对之间的最短路径长度。

  5. 负权边的处理与负权回路检测
    题目假设图中不存在负权回路。如果存在负权回路，则最短路径的概念会变得没有意义，因为可以无限次绕行该回路使得路径长度趋于负无穷。
    虽然本算法不允许负权回路，但它可以处理负权边。算法结束后，我们可以通过检查 dist 矩阵的主对角线来辅助检测负权回路：如果存在某个顶点i，使得 dist[i][i] < 0，则说明图中存在一个经过顶点i的负权回路。因为到自身的距离理应始终为0，出现负数意味着存在一条绕回自身的负权路径。

总结
Floyd-Warshall算法通过三层循环，以动态规划的方式系统地考虑了所有顶点作为中间点的可能性，最终计算出所有顶点对之间的最短路径。它的时间复杂度为O(n³)，空间复杂度为O(n²)。虽然对于稀疏图来说效率不如运行n次Dijkstra算法，但其代码极其简洁，并且能直接处理带有负权边（无负权回路）的图，是其显著优势。

Floyd-Warshall算法求解所有顶点对最短路径 题目描述 给定一个带权有向图，图中可能包含负权边，但不存在负权回路。要求计算图中任意两个顶点之间的最短路径长度。也就是说，我们需要一个矩阵作为结果，其中第i行第j列的元素表示从顶点i到顶点j的最短路径的权值之和。 解题思路 我们将采用动态规划的方法来解决这个问题。核心思想是：逐步考虑将每个顶点作为中间顶点，来更新任意两点间的最短路径估计值。 状态定义 我们定义一个二维数组 dist ，其中 dist[k][i][j] 表示：在考虑前k个顶点（即顶点0, 1, ..., k-1）作为中间顶点的情况下，从顶点i到顶点j的最短路径长度。 然而，我们可以通过重用同一个二维数组来节省空间，将状态优化为 dist[i][j] ，并在算法过程中不断更新它。此时， dist[i][j] 表示当前状态下（即已经考虑过某些中间顶点后）的i到j的最短路径估计值。 初始状态（k=0） 在没有任何中间顶点可用时，从i到j的最短路径有两种情况： 如果i等于j，那么路径长度为0。 如果i不等于j，那么最短路径就是连接i和j的边的权值。如果不存在直接的边，我们先用一个很大的数（比如无穷大）来表示不可达。 因此，我们初始化距离矩阵 dist ： dist[i][i] = 0 （顶点到自身的距离为0） 对于每条边 (u, v, w)（表示从u到v有一条权值为w的边）， dist[u][v] = w 对于其他情况， dist[i][j] = 无穷大 状态转移方程（核心步骤） 现在，我们开始逐个考虑将每个顶点k（从0到n-1）加入允许的中间顶点集合。 对于每一对顶点(i, j)，我们检查是否存在一条路径，通过新加入的顶点k，能够比当前已知的路径更短。 具体来说，对于每一对(i, j)，我们比较： 不经过k的当前最短路径 ： dist[i][j] （即在上一步状态下的值） 经过k的新路径 ：这条路径是从i到k，再从k到j。其长度为 dist[i][k] + dist[k][j] （注意，这里的 dist[i][k] 和 dist[k][j] 是在当前步骤中已经更新过的，意味着它们本身可能已经利用了之前加入的中间顶点，从而保证了最优子结构）。 我们选择两者中较小的那个作为新的最短路径估计值。 状态转移方程 为： dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 算法步骤 基于以上思路，算法的具体步骤非常清晰： a. 初始化距离矩阵 dist ，如上所述。 b. 循环k，从0到n-1（n为顶点总数）： 对于每一个k，循环每一对顶点(i, j)（i和j都从0到n-1）： 如果 dist[i][k] 和 dist[k][j] 都不是无穷大（即i到k和k到j是可达的），并且 dist[i][k] + dist[k][j] 小于当前的 dist[i][j] ： 那么更新 dist[i][j] = dist[i][k] + dist[k][j] 。 c. 循环结束后， dist 矩阵中存储的就是所有顶点对之间的最短路径长度。 负权边的处理与负权回路检测 题目假设图中不存在负权回路。如果存在负权回路，则最短路径的概念会变得没有意义，因为可以无限次绕行该回路使得路径长度趋于负无穷。 虽然本算法不允许负权回路，但它可以处理负权边。算法结束后，我们可以通过检查 dist 矩阵的主对角线来辅助检测负权回路：如果存在某个顶点i，使得 dist[i][i] < 0 ，则说明图中存在一个经过顶点i的负权回路。因为到自身的距离理应始终为0，出现负数意味着存在一条绕回自身的负权路径。 总结 Floyd-Warshall算法通过三层循环，以动态规划的方式系统地考虑了所有顶点作为中间点的可能性，最终计算出所有顶点对之间的最短路径。它的时间复杂度为O(n³)，空间复杂度为O(n²)。虽然对于稀疏图来说效率不如运行n次Dijkstra算法，但其代码极其简洁，并且能直接处理带有负权边（无负权回路）的图，是其显著优势。