最短路Floyd讲解

EZ_XHX · 2023-09-03 12:16:18 · 个人记录

我们讲述一个最短路算法— Floyd

这个算法的本质就是每次去增加一个新点,去更新所有点的最短路。

为什么正确? 我们考虑如下的证明：

对于路径 (i,j) 而言，我们当前枚举到了 k 。

每次都是去尝试一个新点， (i,k) 与 (k,j) 的路径一定是此时的最短路，所以新的 (i,j) 必经过 k 的路径一定是最短路。那为什么我们要用 k\to i \to j 的枚举顺序呢？因为这样你枚举到 k 时之前经过 1,2,\cdots k-1 的路径肯定已经枚举完了，所以说成立。

基于 Floyd 的本质，我们来看一道比较经典的题：

Luogu P1119

给定一张无向带权图，每个点有个修复日期 t_i ，在此之前不可经过，给定 q 个询问 i\to j 于第 k 天的最短路。

我们可以先把询问离线下来，然后每当一个点被修建后，我们针对这个点作为 k (中转点) 跑一遍 Floyd ,

那么这个题其实就是考验你是否理解基础算法的本质了。

与其类似的还有道题，留为思考：

给定一个无向带权图，点有点权，边有边权，定义 i\to j 的路径权值为所有边的边权加上路径上点权最大的点，求出所有点对 (i,j) 的最短路

Floyd 求最小环

我们现在来想一个问题：

给定一个无向图，求出包含给定点的最小环 (边数大于 2 )，要求复杂度 O(n^3) 。

具体而言，我们可以对于与 1 相连的每一条边断开，由于重边已经被合并，这一步的复杂度为 O(n)，然后从 1 节点开始向每个点跑 dijkstra 复杂度 O(n^2)

我们假设与其相连的点为 t 则最后答案为:

那么我们现在要求全局的最小环该怎么去做?

我们可以去找到这个环上编号最大的点 i ，然后去枚举与它相连的任意两条边，这两条边所连的点必须保证编号小于 i ,假设这两个点的编号为 j,k 则最后答案为：

我们可以在 Floyd 时顺便处理出来。

for(int k=1;k<=n;++k){
    for(int i=1;i<k;++i){
        for(int j=1;j<i;++j) ans=min(ans,1ll*e[i][k]+1ll*e[j][k]+1ll*f[i][j]); 
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    }
}

Floyd 在传递闭包的用途

何为传递闭包?

给定一个有向图，每次给定询问 (i,j) 询问 i 能否到达 j 。

这个可以用 O(n^3) 的 Floyed 去求：

for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
             f[i][j]= (f[i][j]||(f[i][k]&&f[k][j])); 

例题： 给定一个 n 个点的 DAG 图 ，边 i\to j 表示 i 打败了 j 问最后能确定多少点的排名。

定义 win_u 表示比 u 强的人的数量 , lose_u 表示比 u 弱的人的数量，如果 u 可以确定排名，那么：

对于每个点的 win 与 lose 我们可以用 dfs O(nm) 去求，也可以用传递闭包 O(n^3) 去求。

Floyd 与倍增的结合

例题一：

Luogu P1613

给定一个有向图，起点为 1 ，每次可以走 2^k 条边（k \in N) ，问到 n 的最短路。

我们可以定义 f_{p,i,j} 表示经过 2^p 步 i 能否到达 j 。这个东西很好推：

for(int i=1;i<=65;++i){
    for(int j=1;j<=n;++j){
         for(int k=1;k<=n;++k){
            for(int z=1;z<=n;++z){
                vis[i][j][k]=vis[i][j][k]|| (vis[i-1][j][z]&&vis[i-1][z][k]);
            }
        }
    }
}

然后如果：

我们就向 i,j 连一条边权为 1 的边，然后进行广搜就行。

广搜处理边权相同的最短路之所以正确，是因为最遍历到的代表的一定是最短路，且到源点最短路越小越先出队。

例题二：

给定一个无向图 ，询问 s 到 t 经过 k 条边的最短路。

针对部分分，我们可以在 dij 的同时记录一下走过的步数 ，正解的话，我们可以定义 f_{p,i,j} 表示经过 2^p 步 i 到 j 的最短距离,然后再将 k 进行二进制拆分，随后进行动态规划，定义 dis_u 表示源点到 u 的最短路。如果 p 这一位是 1 那么进行如下转移：

或者我们也可以进行矩阵快速幂来优化 DP ，定义 f_p 为最多走 p 步的最短路矩阵，我们一开始知道 f_1，最后只需要求出 f_k 即可。

前一种做法是后一种做法的本质。

例题三： 给定一个有向带权图，然后让你找出点数最小的负环。

由于环的点数等于边数，我们可以将点数最小转化为边数最少。

还是一样，我们可以定义 f_{p,i,j} 表示经过 2^p 条边 i 到 j 的最短距离。然后可以去二分点数然后去凑进行转移，复杂度 O((logn)^2n^3) ，但是可以做到 O(logn\times n^3) 就是直接根据倍增求 lca 的思想去找到那个满足条件的最小值就行。

留一道思考题，与刚才思路十分相似：

给定一个无向带权图，让你求出经过边数最小的边权之和大于等于 m 的路径。