「学习笔记」Floyd 的应用

求最短路

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