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;
}