Floyd 算法
原理
Floyd 算法用来求出任意两个节点之间的最短路。
优点：代码少，思维简单，适用于除了负环以外的任何图。
缺点：时间复杂度为 \(O(n ^ 3)\)，空间复杂度为 \(O(n ^ 2)\)。
而 Floyd 的核心原理是用动态规划实现的，定义一个二维数组 \(f_{i, j}\)，遍历图上的所有点 \(k\)，可以得到如下公式：
\[f[i][j] = min(f[i][j], f[i][k] + f[k][j]) \]代码实现
for (int k = 1; k <= n; k++)
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]);
扩展应用
传递闭包
定义
给定一个不包含自环的有向图，其中一张图的邻接矩阵定义为一个 \(n \times n\) 的矩阵 \(A=(a_{ij})_{n\times n}\)，其中
\[a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right. \]一张图的传递闭包定义为一个 \(n\times n\) 的矩阵 \(B=(b_{ij})_{n\times n}\)，其中
\[b_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right. \]解释
同样通过 Floyd 的过程，只不过将 \(\min\) 运算改为了 \(\or\) 运算。
C++ 自带的 bitset 可以仅通过两重循环得到结果。
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (f[i][k]) f[i] = f[i] | f[k];
最小环问题
定义
给定一个正权无向图，找一个最小权值和的环。
解释
我么们定义 \(g_{i, j}\) 表示 \(i\) 点到 \(j\) 点的初始距离，\(dis_{i, j}\) 表示 \(i\) 点到 \(j\) 点的最短距离。
通过 Floyd 算法的四层代码可知，当我们枚举到 \(k_i\) 时，则已经得到了前 \(k - 1\) 个点的最短路径，我们在所有小于 k 的点之中遍历 \(i\) 和 \(j\)，他们的环就可以表示为：
\[dis_{i, j} + g_{i, k} + g_{k, j} \]我们只需要在每一层的 Floyd 前遍历一次 \(k - 1\) 点中的最小环，就可以减少一维的空间复杂度。
代码
signed main()
{
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m --)
{
int a, b, c; cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c)
}
memcpy(d, g, sizeof d);
int res = INF;
for (int k = 1; k <= n; k ++)
{
for (int i = 1; i < k; i ++)
for (int j = i + 1; j < k; j ++)
res = min(res, d[i][j] + g[i][k] + g[k][j]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j]);
}
if (res == INF) cout << "No solution.";
else cout << res << '\n';
return 0;
}