Floyd-Warshall 全源最短路算法
Floyd-Warshall 全源最短路算法
模板题链接:B3647 【模板】Floyd ,不过并不是很合格的一个模板题。
Floyd-Warshall 算法简称 Floyd 算法,对于给定的带权图 \(G=(V,E)\) ,边权 \(w:E\to \mathbb{R}\) ,
Floyd 算法能在 \(O(|V|^3+|E|)\) 的时间复杂度,和 \(O(|V|^2)\) 的空间复杂度内,计算出全源最短路。
Floyd 算法虽然不擅长处理节点数较多的图,但是由于它不依赖于边的数量,因此还是有一定的优势的。
Floyd 的原理很简单,就是利用动态规划(Dynamic Programming, DP)的思想。
记 \(f(k,i,j)\) 为考虑前 \(k\) 个点时,\(i\) 到 \(j\) 的最短路(的长度),初始值设为 \(+\infty\) 。
这里前 \(k\) 个点的意思是,我们按某个顺序依次考虑每个节点,当前考虑到第 \(k\) 个点。
边界 \(f(k,i,i)=0\) ,以及对于 \(\forall e(i,j) \in E\) 有 \(f(0,i,j)= \min\{w(i,j)\}\) ,这里的 \(\min\) 是为了判重边。
考虑转移。我们考察第 \(k\) 个点对最短路的贡献,显然是通过 \(k\) 的某条路径更新了这一轮的最短路。
换言之,考虑前 \(k-1\) 个点所得出的 \(i\) 到 \(j\) 的最短路,可能经由 \(k\) 这个点中转,形成了新的最短路,即 \[ f(k,i,j) = \min\left(f(k-1,i,j), f(k-1, i, k) + f(k - 1, k, j)\right) \] 注意到每次转移我们只需要 \(k\) 和 \(k-1\) 的数据,因此我们只需要开两个二维数组就好了。
没了,就这么简单,这就是 Floyd 。
模板题的代码:(这道题是无向图、边权为正数,且保证了两点必有路径,其实 Floyd 完全无所谓这些条件)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(111))
int n, m, a[N][N], b[N][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m; memset(a, 0x3f, sizeof(a));
rep(i, 1, n) a[i][i] = 0;
rep(i, 1, m)
{
static int u, v, w; cin >> u >> v >> w;
down(a[u][v], w); down(a[v][u], w);
}
memcpy(b, a, sizeof(a));
rep(k, 1, n) rep(i, 1, n) rep(j, 1, n)
{
if(b[i][k] != INF && b[k][j] != INF)
down(b[i][j], b[i][k] + b[k][j]);
}
rep(i, 1, n) rep(j, 1, n) cout << b[i][j] << " \n"[j == n];
return 0;
}


![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p164.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p98.webp)