Floyd 算法

原理

Floyd 算法用来求出任意两个节点之间的最短路。

优点：代码少，思维简单，适用于除了负环以外的任何图。

缺点：时间复杂度为 $O(n ^ 3)$，空间复杂度为 $O(n ^ 2)$。

而 Floyd 的核心原理是用动态规划实现的，定义一个二维数组 $f_{i, j}$，遍历图上的所有点 $k$，可以得到如下公式：

$$f[i][j] = min(f[i][j], f[i][k] + f[k][j])$$

代码实现

1
2
3
4

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

扩展应用

传递闭包

定义

给定一个不包含自环的有向图，其中一张图的邻接矩阵定义为一个 $n \times n$ 的矩阵 $A=(a_{ij})_{n\times n}$，其中

$$a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right.$$

一张图的传递闭包定义为一个 $n\times n$ 的矩阵 $B=(b_{ij})_{n\times n}$，其中

$$b_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right.$$

解释

同样通过 Floyd 的过程，只不过将 $\min$ 运算改为了 \or 运算。

C++ 自带的 bitset 可以仅通过两重循环得到结果。

1
2
3

for (k = 1; k <= n; k++)
  for (i = 1; i <= n; i++)
    if (f[i][k]) f[i] = f[i] | f[k];

最小环问题

定义

给定一个正权无向图，找一个最小权值和的环。

解释

我么们定义 $g_{i, j}$ 表示 $i$ 点到 $j$ 点的初始距离，$dis_{i, j}$ 表示 $i$ 点到 $j$ 点的最短距离。

通过 Floyd 算法的四层代码可知，当我们枚举到 $k_i$ 时，则已经得到了前 $k - 1$ 个点的最短路径，我们在所有小于 k 的点之中遍历 $i$ 和 $j$，他们的环就可以表示为：

$$dis_{i, j} + g_{i, k} + g_{k, j}$$

我们只需要在每一层的 Floyd 前遍历一次 $k - 1$ 点中的最小环，就可以减少一维的空间复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    
    while (m --)
    {
        int a, b, c; cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c)
    }
    
    memcpy(d, g, sizeof d);
    int res = INF;
    
    for (int k = 1; k <= n; k ++)
    {
        for (int i = 1; i < k; i ++)
            for (int j = i + 1; j < k; j ++)
                res = min(res, d[i][j] + g[i][k] + g[k][j]);
        
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j]);
    }
    
    if (res == INF) cout << "No solution.";
    else cout << res << '\n';
    return 0;
}