最短路系列：floyd 算法
大家好，我是Weekoder!
最近学了最短路，我来出一个最短路系列辣！
今天的算法是：floyd 算法！
我会用我自己的理解尽量让大家搞懂 floyd 算法。
floyd 算法的用处
floyd 算法是最短路算法之一，适合求解多源最短路径问题。什么是多源最短路径呢？其实就是起点和终点都有多个的最短路径算法，在计算完之后可以以 \(O(1)\) 的速度获得任意两点之间的最短路径。
另外，floyd 算法的本质其实是动态规划。
floyd 算法的思想
在图中，我们往往需要求出某个点到另一个点的最短路径，这时候我们就可以使用 floyd 算法。
我们来想一想该怎么用最直接的方式求出两点之间的最短路径。假设城市 A 和城市 B 之间的距离是 \(10\)，那我们首先可以想到直接从 A 走到 B，距离为 \(10\)。这时候，如果有一个城市 C，A 到 C 的距离是 \(3\)，C 到 B 的距离是 \(5\)，我们就可以先来到城市 C，再前往城市 B。这样的总距离是 \(3+5=8\)，比之前的 \(10\) 要更优。
那到底为什么会更优呢？是因为有了城市 C 这样一个中转站，使得总距离缩短了。我们仔细思考一下，在图上两点之间的直接距离往往不是最优的，而是要经过一些中转站，使得总路程进一步缩短。floyd 算法实际上就是枚举了这些中转站，并用状态转移方程求解。
floyd 算法的实现
我们知道了要使两点之间的距离缩短，就必须引入中转站。现在，我们来看一下 floyd 算法是怎么实现的。
先看部分代码如下：
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
// 状态转移方程
可以看到，这里有三层循环。
-
第一层循环的 \(k\) 是在枚举每个中转站。
-
第二层循环的 \(i\) 是在枚举起点。
-
第三层循环的 \(j\) 是在枚举终点。
最后在循环里执行状态转移方程。
有一个重点：中转站必须在最外层枚举！我们要枚举中转站逐个更新，如果在外层枚举起点和终点，会导致更新不完全。
那么，状态转移方程又是什么呢？
我们只需要在直接到达的路径和间接到达的路径中取 min 就行了：
\[e_{i,j}=\min(e_{i,j},e_{i,k}+e_{k,j}); \]这里的 \(e_{i,j}\) 表示 \(i\) 点到 \(j\) 点目前的最短路径。
状态转移方程用人话讲就是在 \(i\) 直接到 \(j\) 和 \(i\) 先到 \(k\) 再从 \(k\) 到 \(j\) 中取 min。
接下来讲一下二维数组 \(e\) 的初始化。
首先，我们知道一个点到自己的距离是 \(0\)，所以有：
\[e_{i,i}=0; \]而其他的数我们可以先设为 INF（无穷大），所以又有：
\[e_{i,j}=+\infty,\space i\ne j; \]而当我们输入一条边时，一般会有三个参数 \(u,v,w\)，代表从 \(u\) 到 \(v\) 有一条权值为 \(w\) 的边，无向边构建如下：
\[e_{u,v}=e_{v,u}=w; \]有向边构建如下：
\[e_{u,v}=w; \]例题实践
- 难度一颗星：B3647 【模板】Floyd
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 105, INF = 1 << 30;
int n, m, e[N][N];
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (e[i][k] != INF && e[k][j] != INF)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[i][j] = i == j ? 0 : INF;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[u][v] = e[v][u] = w;
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout << e[i][j] << " ";
cout << "\n";
}
return 0;
}
注意要加上判断：\([e_{i,k}\ne \infty \space \text{and} \space e_{k,j}\ne \infty]\)，否则会溢出，变成负数。
我们所说的无穷大可以用 \(2^{30}\) 来代替。
可以把 floyd 核心部分封装成函数。
- 难度三颗星：P1364 医院设置
可以自己看题解理解哦~
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 105, INF = 1 << 30;
int n, e[N][N], ans = INF, w[N];
void FloydInit() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[i][j] = i == j ? 0 : INF;
}
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (e[i][k] != INF && e[k][j] != INF)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
int main() {
cin >> n;
FloydInit();
for (int i = 1; i <= n; i++) {
int u, v;
cin >> w[i] >> u >> v;
if (u)
e[i][u] = e[u][i] = 1;
if (v)
e[i][v] = e[v][i] = 1;
}
floyd();
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= n; j++)
if (e[i][j] != INF)
sum += e[i][j] * w[j];
ans = min(ans, sum);
}
cout << ans;
return 0;
}
- 挑战——难度四颗星：P1828 [USACO3.2] 香甜的黄油 Sweet Butter
与上一题相似，类似加强版。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, INF = 1 << 30;
int n, p, m, e[N][N], cow[N], ans;
void FloydInit() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[i][j] = i == j ? 0 : INF;
}
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (e[i][k] != INF && e[k][j] != INF)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
int main() {
cin >> p >> n >> m;
FloydInit();
for (int i = 1; i <= p; i++)
cin >> cow[i];
for (int i = 1; i <= m; i++) {
int a, b, d;
cin >> a >> b >> d;
e[a][b] = e[b][a] = min(e[a][b], d);
}
floyd();
int ans = INF;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= p; j++) {
if (e[i][cow[j]] == INF) {
sum = INF;
break;
}
sum += e[i][cow[j]];
}
ans = min(ans, sum);
}
cout << ans;
return 0;
}
最后
floyd 算法适合需要多次访问任意两点之间最短路径的问题。你，学会了吗？