求最短路
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]);
}
}
}
求最小环
过程
记原图中 \(u,v\) 之间边的边权为 \(val\left(u, v\right)\)。
我们注意到 Floyd 算法有一个性质:在最外层循环到点 \(k\) 时(尚未开始第 \(k\) 次循环),最短路数组 dis
中,\(dis_{u, v}\) 表示的是从 \(u\) 到 \(v\) 且仅经过编号在 \(\left[1, k\right)\) 区间中的点的最短路。
由最小环的定义可知其至少有三个顶点,设其中编号最大的顶点为 \(w\),环上与 \(w\) 相邻两侧的两个点为 \(u,v\),则在最外层循环枚举到 \(k = w\) 时,该环的长度即为 \(dis_{u,v}+val\left(v,w\right)+val\left(w,u\right)\)。
故在循环时对于每个 \(k\) 枚举满足 \(i < k ,j < k\) 的 \(\left(i,j\right)\),更新答案即可。
时间复杂度: \(O_{n^3}\)
int floyd(int n) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
dis[i][j] = val[i][j];
}
}
int ans = inf;
for (int k = 1; k <= n; ++ k) {
for (int i = 1; i < k; ++ i) {
for (int j = 1; j < i; ++ j) {
ans = min(ans, dis[i][j] + val[i][k] + val[k][j]);
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
return ans;
}
for (int k = 1; k <= n; ++ k) {
for (int i = 1; i < k; ++ i) {
for (int j = 1; j < i; ++ j) {
ans = min(ans, dis[i][j] + val[i][k] + val[k][j]);
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
第一个循环为找最小环,第二个循环为正常更新 dis
数组。
求任意两点的最短路径数
记 g[x][y]
数组,再求最短路的时候一起维护即可。
for (int k = 1; k <= n; ++ k) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (dis[i][k] + dis[k][j] > dis[i][j]) {
continue;
}
else if (dis[i][k] + dis[k][j] < dis[i][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
g[i][j] = g[i][k] * g[k][j];
}
else {
g[i][j] += g[i][k] * g[k][j];
}
}
}
}
传递闭包
即已知一个有向图中任意两点之间是否有连边,要求判断任意两点是否连通。
for (int k = 1; k <= n; ++ k) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
dis[i][j] |= dis[i][k] & dis[k][j];
}
}
}
标签:right,int,短路,笔记,学习,Floyd,left,循环,dis
From: https://www.cnblogs.com/yifan0305/p/17365299.html