算法描述
三个破变量，一共就十行。编程十分钟，运行一晚上。
很多人认为 Floyd 就是简单的动态规划，甚至有人直接把它当模板背了下来，导致不会变通而 WA 了 P1119。然而其实大多数初学者包括我一开始都理解错了它，包括原理。
算法实现
定义 表示只包含前 个节点时 到 的最短路。而加不加入这个 号元素前后有什么区别呢？无非就是某两个点的最短路通过 号点松弛出了更有的最短路嘛。于是就有了经典代码：
1
2
3
4
5
6
7
8
9
| void Floyd(){
for(ll k = 1; k <= n; k ++){
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
|
那么如何初始化呢？如果
到
有路，就初始化为边长。否则初始化为最大值。
1
2
3
4
5
6
7
| for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
if(i == j)dis[i][j] = 0;
else if(gph[i][j])dis[i][j] = gph[i][j];
else dis[i][j] = INF;
}
}
|
这就完了吗？这值得写博客吗？当然不值。
虽然我本来就是给自己写来复习的
Floyd应用
Floyd解决传递闭包问题
题目传送门
在有向图中，定义 如果是 1，则表示 能到达 ，否则反之。
这该如何解决呢？转换一下定义。
定义 表示只有前 个点时 能否到达 。同理，加入了一个元素 之后无非就是有一组 能通过它到达 了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void Floyd(){
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
if(graph[i][j])d[i][j] = 1;
else d[i][j] = 0;
}
}
for(ll k = 1; k <= n; k ++){
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
}
}
}
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
cout << d[i][j] << " ";
}
cout << "\n";
}
}
|
Floyd求最小环
依旧是改定义： 为前 个节点中可以确定的最小环的大小。则匹配最短路，可以在算最短路之后算环了，可以理解为以 为一个顶点，由 可以到达的 和 以及 也就是最短路构成的环。然后枚举已经算出最短路的 即可。
例题就是 P2738 篱笆回路。这题输入特别逆天，所以给了完整代码。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN = 305;
const ll INF = 2147483647;
struct Edge{
ll u, v, w;
bool lside[MAXN], rside[MAXN];
}edge[MAXN];
ll adj[MAXN][MAXN], father[MAXN], m, n, idx[MAXN], dis[MAXN][MAXN];
ll find(ll x){
if(father[x] == x)return x;
return father[x] = find(father[x]);
}
void merge(ll x, ll y){
father[find(x)] = find(y);
}
ll Floyd(){
ll ans = INF;
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
if(!dis[i][j])dis[i][j] = INF;
if(!adj[i][j])adj[i][j] = INF;
}
}
for(ll i = 1; i <= n; i ++){
adj[i][i] = dis[i][i] = 0;
}
for(ll k = 1; k <= n; k ++){
for(ll i = 1; i <= k - 1; i ++){
for(ll j = i + 1; j <= k - 1; j ++){
ans = min(ans, adj[i][k] + adj[k][j] + dis[i][j]);
}
}
for(ll i = 1; i <= n; i ++){
for(ll j = 1; j <= n; j ++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
return ans;
}
int main(){
cin >> m;
for(ll i = 1; i <= m; i ++){
ll s, len, numl, numr, id;
cin >> s >> len >> numl >> numr;
edge[s].u = s * 2 - 1;
edge[s].v = s * 2;
edge[s].w = len;
for(ll j = 1; j <= numl; j ++){
cin >> id;
edge[s].lside[id] = 1;
}
for(ll j = 1; j <= numr; j ++){
cin >> id;
edge[s].rside[id] = 1;
}
}
for(ll i = 1; i <= 250; i ++){
father[i] = i;
}
for(ll i = 1; i <= m; i ++){
for(ll j = 1; j <= m; j ++){
if(i == j)continue;
if(edge[i].lside[j] && edge[j].lside[i]){
merge(edge[i].u, edge[j].u);
}
if(edge[i].lside[j] && edge[j].rside[i]){
merge(edge[i].u, edge[j].v);
}
if(edge[i].rside[j] && edge[j].lside[i]){
merge(edge[i].v, edge[j].u);
}
if(edge[i].rside[j] && edge[j].rside[i]){
merge(edge[i].v, edge[j].v);
}
}
}
for(ll i = 1; i <= 2 * m; i ++){
if(father[i] == i){
idx[i] = ++n;
}
}
for(ll i = 1; i <= m; i ++){
edge[i].u = idx[find(edge[i].u)];
edge[i].v = idx[find(edge[i].v)];
adj[edge[i].u][edge[i].v] = edge[i].w;
adj[edge[i].v][edge[i].u] = edge[i].w;
dis[edge[i].u][edge[i].v] = edge[i].w;
dis[edge[i].v][edge[i].u] = edge[i].w;
}
cout << Floyd() << "\n";
return 0;
}
|
总结
Floyd 算法似乎从方方面面看都很平庸：时间复杂度高达 ，需要空间复杂度耗费较大的邻接矩阵存图，甚至连模板的使用环境都比较小。
然而 Floyd 算法具有较高的灵活性、可读性和可写性。一旦深刻理解了它的原理，就可以加以变通，解决许许多多看似复杂的算法。以上就是例子，希望大家不要想我最初一样，只背了模板，没有思考含义。
Floyd 算法之所以被发明出来，并不是因为他比 Dijkstra 更快，比 SPFA 更好理解，而是因为，他善啊……
推荐例题：洛谷 P1119 灾后重建，P1841 重要的城市
