Skip to main content

图论算法：Floyd-Warshall 算法

Aiden L.7/27/24About 3 min算法算法图论最短路Floyd动态规划

什么是 Floyd-Warshall 算法？

Floyd-Warshall 算法（简称 Floyd 算法）是一种用于计算 所有顶点对之间最短路径 的算法。与 Dijkstra 和 SPFA 不同，它不是单源最短路算法，而是一次性计算出图中任意两点之间的最短距离。

Floyd 算法可以正确处理带有 负权边 的图，但不能处理带有 负环 的图。它非常适合用于稠密图。

核心思想：动态规划

Floyd 算法的本质是一个动态规划。我们定义一个二维数组 dp[k][i][j]，表示从顶点 i 到顶点 j，只允许经过编号从 1 到 k 的顶点作为中间点时，所能得到的最短路径长度。

状态转移方程如下： dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

这个方程的含义是：从 i 到 j，若只允许经过 1...k 作为中间点，其最短路径有两种可能：

  1. 不经过顶点 k，那么最短路径就是 dp[k-1][i][j]。
  2. 经过顶点 k，那么路径就被分为 i -> k 和 k -> j 两段，最短路径就是这两段之和 dp[k-1][i][k] + dp[k-1][k][j]。

我们在这两种可能中取一个最小值。

由于 dp[k] 的计算只依赖于 dp[k-1]，我们可以通过滚动数组的思想，将 k 这一维度优化掉，得到一个更简洁的二维形式。

算法流程

  1. 初始化:

    • 创建一个二维数组 dist[i][j]，用于存储任意两点 i 和 j 之间的最短距离。
    • 如果 i 和 j 之间有直接的边，则 dist[i][j] 等于该边的权重。
    • 如果 i == j，则 dist[i][j] = 0。
    • 其他情况，dist[i][j] 为无穷大。

  2. 三重循环:

    • 最外层循环 k 从 1 到 N（k 是作为中间点的顶点）。
    • 内两层循环 i 从 1 到 N 和 j 从 1 到 N。
    • 在循环中，执行松弛操作：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

循环结束后，dist[i][j] 中存储的就是从 i 到 j 的最短路径长度。

C++ 伪代码

#include <vector>
#include <algorithm>

const int INF = 1e9; // 一个足够大的数

void floydWarshall(int n, std::vector<std::vector<int>>& dist) {
    // dist 数组需要预先初始化
    // dist[i][j] = weight if edge (i,j) exists
    // dist[i][i] = 0
    // dist[i][j] = INF otherwise

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

复杂度分析

  • 时间复杂度: O(N³)，其中 N 是顶点数。这个复杂度使得它不适用于非常大的图。
  • 空间复杂度: O(N²)。

Floyd 算法以其代码简洁、逻辑清晰而著称，是解决全源最短路问题的标准方法。