Floyd 算法——脚踏图论、数学两条船的算法

Floyd 算法简介#

Floyd 算法是一种能在 $\mathcal O(n^3)$ 时间复杂度内求出任意两点间最短路长度的多源最短路算法，又称 $\texttt{Floyd-Warshall}$ 算法或插点法，以它的发明者命名。Floyd 算法基于动态规划，通过穷举 $i$ 节点和 $j$ 节点的所有中继节点 $k$ 进行松弛操作得到最短路径。对于稠密图，它的执行效率会快于 Dijkstra 和 Bellman-Ford 算法。

在初始建图时。对于邻接矩阵 $A$ ， $A_{ij}$ 代表 $i$ 和 $j$ 点间的直连最短路径长度，也就是读入时数据告诉你的两点间的边长；剩下没有直接连接的两点间距离设为正无穷。特别地， $A_{ii}$ 需要初始化为 ${0}$ ，因为从自己出发回到自己的边权为零。

在算法运行过程中，假设当前枚举到点 $i$ 和 $j$ ，算法需要枚举中继点 $k$ 。那么路径 $i\rightarrow j\rightarrow k$ 成为最短距离的必要条件是存在边 $(i,j)$ 和 $(j,k)$ 。若当前 $\operatorname{dis}(i,j)<\operatorname{dis}(i,k)+\operatorname{dis}(k,j)$ ，则将 $\operatorname{dis}(i,j)$ 更新，这一点和 Dijkstra 是类似的。

Floyd 算法的基本模板如下：

1
for (int k = 1; k <= n; k++) {
2
  for (int i = 1; i <= n; i++) {
3
    for (int j = 1; j <= n; j++) {
4
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
5
    }
6
  }
7
}

~~只有四层，非常简单。~~

对于 Floyd 算法，还需注意的一点是它的循环次序问题。如果想一次跑出正确结果，那就需要将中继点枚举放在最外层，也就是最外层是 $k$ 循环，剩余的循环只需保证在 $k$ 层内即可，顺序无所谓。而如果是类似于 ikj 次序的循环，那么至多需要两次才能求出正确答案；如果是 ijk 次序，则至多需要求三次。具体参见这篇博客。

Floyd 图论#

Floyd 在图论方面有几大重要作用——求无向图最小环、传递闭包。

P6175 无向图最小环问题#

题目地址：P6175

题目难度：普及/提高-

给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。
输入格式：
第一行两个正整数 $n,m$ 表示点数和边数。
接下来 $m$ 行，每行三个正整数 $u,v,d$ ，表示节点 $u,v$ 之间有一条长度为 $d$ 的边。
输出格式：
输出边权和最小的环的边权和。若无解，输出 No solution.。

假设有一张图：

当 Floyd 算法枚举到中继节点 $k$ 时，且存在边 $(i,j)$ 和 $(k,j)$ 。那么环 $(i,j,k)$ 是有机会成为当前图上的最小环的（注意到图是无向图，若 $i$ 能到 $j$ ，则 $j$ 一定能到达 $i$ ）。若当前环的权值（ $\operatorname{dis}(i,j)+\operatorname{w}(i,k)+\operatorname{w}(k,j)$ ，注意是边权 $w$ ）小于全局最小值，则更新全局最小值。

1
#include <bits/stdc++.h>
2
#define N 110
3
#define INF 0x3f3f3f3f
4
using namespace std;
5

6
typedef long long ll;
7

8
int n, m;
9
ll g[N][N], dist[N][N];
10

11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
    cout.tie(nullptr);
15

16
    memset(g, 0x2a, sizeof g);
17

18
    cin >> n >> m;
19

20
    for (int i = 1; i <= n; i++) g[i][i] = 0;
21

22
    while (m--) {
23
        int u, v;
24
        ll d;
25
        cin >> u >> v >> d;
26
        g[u][v] = g[v][u] = min(g[u][v], d);
27
    }
28

29
    memcpy(dist, g, sizeof dist);
30

31
    ll ans = LLONG_MAX;
32
    for (int k = 1; k <= n; k++) {
33
        for (int i = 1; i < k; i++) {
34
            for (int j = i + 1; j < k; j++) {
35
                ans = min(ans, dist[i][j] + g[i][k] + g[k][j]);
36
            }
37
        }
38
        for (int i = 1; i <= n; i++) {
39
            for (int j = 1; j <= n; j++) {
40
                dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k] + dist[k][j]);
41
            }
42
        }
43
    }
44
    if (ans >= INF) cout << "No solution." << endl;
45
    else cout << ans << endl;
46

47
    return 0;
48
}

B3611 [模板] 传递闭包#

题目地址：B3611

题目难度：普及/提高-

给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。
一张图的邻接矩阵定义为一个 $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.$
输入格式：
输入数据共 $n+1$ 行。
第一行一个正整数 $n$ 。
第 $2$ 到 $n+1$ 行每行 $n$ 个整数，第 $i+1$ 行第 $j$ 列的整数为 $a_{ij}$ 。
输出格式：
输出数据共 $n$ 行。
第 $1$ 到 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数为 $b_{ij}$ 。

~~说句闲话，感觉这个传递闭包和并查集路径压缩好像……~~

我们在用 Floyd 求最短路时，以 $k$ 为中继节点进行的松弛操作其实就指明了一个间接到达的关系：“点 $i$ 可以经过点 $k$ 间接到达点 $j$ ”。因此只需要在 Floyd 内部加入“若存在边 $(i,k)$ 和 $(k,j)$ ，则将传递闭包 $(i,j)$ 置为 ${1}$ ”。

1
#include <bits/stdc++.h>
2
#define N 110
3
using namespace std;
4

5
int g[N][N];
6

7
void floyd(int n) {
8
    for (int k = 1; k <= n; k++) {
9
        for (int i = 1; i <= n; i++) {
10
            for (int j = 1; j <= n; j++) {
11
                if (g[i][k] && g[k][j]) g[i][j] = 1;
12
            }
13
        }
14
    }
15
}
16

17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
    cout.tie(nullptr);
21

22
    int n;
23
    cin >> n;
24
    for (int i = 1; i <= n; i++) {
25
        for (int j = 1; j <= n; j++) {
26
            cin >> g[i][j];
27
        }
28
    }
29

30
    floyd(n);
31

32
    for (int i = 1; i <= n; i++) {
33
        for (int j = 1; j <= n; j++) {
34
            cout << g[i][j] << ' ';
35
        }
36
        cout << endl;
37
    }
38
    return 0;
39
}

P1347 排序#

题目地址：P1347

题目难度：普及+/提高

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示 $A<B,B<C,C<D$ 。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入格式：
第一行有两个正整数 $n,m$ ， $n$ 表示需要排序的元素数量， $2\leq n\leq 26$ ，第 $1$ 到 $n$ 个元素将用大写的 $A,B,C,D,\dots$ 表示。 $m$ 表示将给出的形如 $A<B$ 的关系的数量。
接下来有 $m$ 行，每行有 $3$ 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。
输出格式：
若根据前 $x$ 个关系即可确定这 $n$ 个元素的顺序 yyy..y（如 ABC），输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 $x$ 个关系即发现存在矛盾（如 $A<B,B<C,C<A$ ），输出
Inconsistency found after x relations.
若根据这 $m$ 个关系无法确定这 $n$ 个元素的顺序，输出
Sorted sequence cannot be determined.
（提示：确定 $n$ 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

矛盾情况是诸如： $A<A$ 的情况。

我们把所有的小于关系存在一张邻接矩阵里， $A_{ij}=1$ 所承载的含义就变成了：存在严格小于关系 $A_i<A_j$ 。那么想要求出所有的大小关系，就需要对每个字母能直接或间接导出的所有字母进行比较判断。这道题就可以用传递闭包来处理每个字母间的推导关系。

由于题目的特殊要求，我们选择每次只读入一个大小关系，然后跑一次传递闭包，再对结果进行判断输出。若传递闭包的对角线元素不全为零，代表存在矛盾，直接跳出；若存在点对 $(i,j)$ ，使得 $A_{ij}=0$ ，那么就是一个亚定的关系，需要进一步增加条件，特殊地，若此时已读入所有关系，则输出无解；若对于所有点对 $(i,j)$ 都有 $A_{ij}\neq0$ 且不存在矛盾，那么就可以输出序列了。

对于序列的升序输出，首先枚举 $i$ 。 $i$ 是最小值的充要条件是不存在任何点对 $(i,j)$ 使得 $A_{ij}\neq0$ ，即不存在更小的值。在找到最小值后标记一下，重复查找即可得到整个序列。

1
#include <bits/stdc++.h>
2
#define N 30
3
using namespace std;
4

5
int g[N][N], cpy[N][N];
6
bool st[N];
7
int n, m;
8

9
void floyd() {
10
    memcpy(cpy, g, sizeof g);
11
    for (int k = 1; k <= n; k++) {
12
        for (int i = 1; i <= n; i++) {
13
            for (int j = 1; j <= n; j++) {
14
                if (cpy[i][k] && cpy[k][j]) cpy[i][j] = 1;
15
            }
16
        }
17
    }
18
}
19

20
int check() {
21
    for (int i = 1; i <= n; i++) {
22
        if (cpy[i][i]) return 1;
23
    }
24
    for (int i = 1; i <= n; i++) {
25
        for (int j = 1; j < i; j++) {
26
            if (!cpy[i][j] && !cpy[j][i]) return 0;
27
        }
28
    }
29
    return 2;
30
}
31

32
char getC() {
33
    for (int i = 1; i <= n; i++) {
34
        if (!st[i]) {
35
            bool flag = true;
36
            for (int j = 1; j <= n; j++) {
37
                if (!st[j] && cpy[j][i]) {
38
                    flag = false;
39
                    break;
40
                }
41
            }
42
            if (flag) {
43
                st[i] = true;
44
                return static_cast<char>(i + 'A' - 1);
45
            }
46
        }
47
    }
48
}
49

50
int main() {
51
    ios::sync_with_stdio(false);
52
    cin.tie(nullptr);
53
    cout.tie(nullptr);
54

55
    while (cin >> n >> m, n || m) {
56
        memset(g, 0, sizeof g);
57
        memset(st, false, sizeof st);
58

59
        int t = 0, tmp = 0;
60
        for (int i = 1; i <= m; i++) {
61
            char s[5];
62
            cin >> s;
63
            int a = s[0] - 'A' + 1, b = s[2] - 'A' + 1;
64
            g[a][b] = 1;
65
            floyd();
66
            t = check();
67

68
            if (t) {
69
                tmp = i;
70
                break;
71
            }
72
        }
73
        if (t == 1) cout << "Inconsistency found after " << tmp << " relations." << endl;
74
        else if (t == 0) cout << "Sorted sequence cannot be determined." << endl;
75
        else {
76
            cout << "Sorted sequence determined after " << tmp << " relations: ";
77
            for (int i = 1; i <= n; i++) cout << getC();
78
            cout << "." << endl;
79
        }
80
    }
81
    return 0;
82
}

Floyd 数学#

因为 Floyd 算法基于邻接矩阵存图，所以它可以通过矩阵运算来实现一些图上的计数问题。

P2886 [USACO07NOV] Cow Relays G#

题目地址：P2886

题目难度：提高+/省选-

给定一张 $T$ 条边的无向连通图，求从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度。
输入格式
第一行四个正整数 $N,T,S,E$ ，意义如题面所示。
接下来 $T$ 行每行三个正整数 $w,u,v$ ，分别表示路径的长度，起点和终点。
输出格式：
一行一个整数表示图中从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度。

类比矩阵乘法的定义式： $C_{ij}=\sum\limits_{k=1}^{n}A_{ik}B_{kj}$ 。是不是很像松弛操作时的下标？其实将邻接矩阵乘幂就可以看作枚举可达的两点路径。相应的，在无权图中求诸如“从起点到终点经过 $N$ 条边的路径总数”就可以将邻接矩阵乘 $N$ 次幂。但如果是像这道题，是带边权的形式，又该如何操作？

我们把矩阵乘法重新变成如下的形式：

C_{ij}=\operatorname{min}(C_{ij},A_{ik}+B_{kj})

就可以做了，有点像在矩阵乘幂的同时跑最短路。将上文所说的无权图情况和带权 Floyd 有机结合了起来。加入快速幂可以进一步优化。需要注意的是矩阵的初始化。

1
#include <bits/stdc++.h>
2
#define N 210
3
using namespace std;
4

5
typedef long long ll;
6

7
struct Matrix {
8
    ll mat[N][N];
9

10
    Matrix() {
11
        memset(mat, 0, sizeof mat);
12
    }
13

14
    void init() {
15
        for (int i = 1; i <= N - 1; i++) mat[i][i] = 1;
16
    }
17

18
    void zero() {
19
        for (int i = 1; i <= N - 1; i++) mat[i][i] = 0;
20
    }
21

22
    void inf() {
23
        memset(mat, 0x2a, sizeof mat);
24
    }
25
};
26

27
int n, t, S, E;
28
int cnt = 0;
29
Matrix g;
30

31
Matrix operator*(const Matrix &A, const Matrix &B) {
32
    Matrix C;
33
    C.inf();
34
    for (int k = 1; k <= t; k++) {
35
        for (int i = 1; i <= t; i++) {
36
            for (int j = 1; j <= t; j++) {
37
                C.mat[i][j] = min(C.mat[i][j], A.mat[i][k] + B.mat[k][j]);
38
            }
39
        }
40
    }
41

42
    return C;
43
}
44

45
Matrix qpow(Matrix a, int b) {
46
    Matrix res;
47
    res.inf();
48
    res.zero();
49
    while (b) {
50
        if (b & 1) res = res * a;
51
        a = a * a;
52
        b >>= 1;
53
    }
54
    return res;
55
}
56

57
int main() {
58
    ios::sync_with_stdio(false);
59
    cin.tie(nullptr);
60
    cout.tie(nullptr);
61

62
    cin >> n >> t >> S >> E;
63

64
    g.inf();
65

66
    map<int, int> mp;
67
    mp[S] = ++cnt;
68
    mp[E] = ++cnt;
69
    S = mp[S], E = mp[E];
70
    for (int i = 1; i <= t; i++) {
71
        ll w;
72
        int u, v;
73
        cin >> w >> u >> v;
74
        if (!mp.count(u)) mp[u] = ++cnt;
75
        if (!mp.count(v)) mp[v] = ++cnt;
76

77
        u = mp[u], v = mp[v];
78

79
        g.mat[u][v] = g.mat[v][u] = min(g.mat[u][v], w);
80
    }
81
    g = qpow(g, n);
82
    cout << g.mat[S][E] << endl;
83
    return 0;
84
}

小结#

Floyd 作为一个最短路算法具备了图论和数学计算的双重功能，只是在实际运用中需要留意它 $\mathcal O(n^3)$ 的时间复杂度。对于较大的点数/稀疏图，建议使用 Dijkstra 或 Bellman-Ford；但若是一个稠密图，或者是点数较少，且需要求出一些奇奇妙妙的数据，那么就可以考虑一下 Floyd。

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

Floyd 算法——脚踏图论、数学两条船的算法

Floyd 算法简介#

Floyd 图论#

P6175 无向图最小环问题#

B3611 [模板] 传递闭包#

P1347 排序#

Floyd 数学#

P2886 [USACO07NOV] Cow Relays G#

小结#

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

Floyd 算法——脚踏图论、数学两条船的算法

Floyd 算法简介#

Floyd 图论#

P6175 无向图最小环问题#

B3611 [模板] 传递闭包#

P1347 排序#

Floyd 数学#

P2886 [USACO07NOV] Cow Relays G#

小结#

支持与分享

评论区

音乐

目录

JustPureH₂O