Floyd之蓝桥公园

Floyd

Floyd算法是一种用于解决“所有点最短路径”问题的算法。这是一个动态规划算法，可以在任何包含向量和非负权重的图中使用。它的时间复杂度是 $O(n^3)$ ，其中 $n$ 是图中的节点数。

首先，我们定义一个二维数组 $g[i][j]$ 表示从 $i$ 到 $j$ 的最短距离，初始时如果 $i$ 和 $j$ 之间有直接的边，那么 $g[i][j]$ 是这条边的权值，否则 $g[i][j]$ 为无穷大。对于任意的 $i$ ， $g[i][i]$ 应当初始化为0。这就是我们的初始状态。

Floyd算法的关键思想是：对于每个顶点k，我们尝试使用这个顶点作为所有其他点对（i，j）的中间点。也就是说，我们检查对于所有的点对（i，j），是否通过顶点k可以找到一条从i到j的更短路径。如果可以，我们就更新 $g[i][j]$ 的值。

具体的，算法的步骤如下：

我们首先选择一个顶点k。
然后，我们遍历所有的点对（i，j）。
对于每个点对（i，j），我们计算通过顶点k的路径的长度，也就是g[i][k]+g[k][j]。
如果这个长度小于当前的g[i][j]，那么我们就更新g[i][j]。也就是说，我们找到了一条从i到j的更短路径，那么我们就用这个更短的距离替换原来的g[i][j]。

这个过程会重复n次，其中n是顶点的数量。每次迭代，我们都选择一个新的顶点k，并尝试使用这个顶点更新所有的最短路径。因此，算法的时间复杂度是 $O(n^3)$ 。

最后，当算法结束时，g[i][j]就是从顶点i到顶点j的最短路径的长度。

例如假设我们有以下的图：

1 - 2
|   |
4 - 3

其中，节点1到节点2的距离是1，节点2到节点3的距离是2，节点3到节点4的距离是1，节点4到节点1的距离是2。节点1到3、2到4的距离都是无穷大。

在运行Floyd算法后，我们会得到以下结果：

从顶点 1 到其他所有顶点的最短路径长度为：到自身是 0，到 2 是 1，到 3 是 3，到 4 是 2。
从顶点 2 到其他所有顶点的最短路径长度为：到自身是 0，到 1 是 1，到 3 是 2，到 4 是 3。
从顶点 3 到其他所有顶点的最短路径长度为：到自身是 0，到 2 是 2，到 1 是 3，到 4 是 1。
从顶点 4 到其他所有顶点的最短路径长度为：到自身是 0，到 3 是 1，到 2 是 3，到 1 是 2。

这就是Floyd算法的主要思想和实现。通过这个算法，我们可以计算出图中任意两点之间的最短路径。

注意，Floyd算法不仅可以用于求解最短路径问题，还可以用于解决其他相关问题。比如，如果我们想要知道是否存在负权环（这在某些问题是非法的），我们只需在算法结束后检查对角线上是否存在负数。如果存在那么图中就存在负权环。

此外，Floyd算法还可以求解图的传递闭包问题。所谓传递闭包，就是对于图中的每个点对（i，j），如果从i可以到达j，则g[i][j]=1，否则g[i][j]=0。此时，我们只需将Floyd算法中的 min 操作改为 or 操作，+ 操作改为 and 操作，就可以求解传递闭包问题了。

总的来说，Floyd算法是一种非常强大的算法，可以解决许多与图和网络相关的问题。虽然它的时间复杂度较高，但是对于顶点数量不是非常大的问题，它的效率是可以接受的。特别是在蓝桥杯比赛中有奇效，由于蓝桥杯是OI赛制，即过部分数据得部分分，而又因为Floyd易记忆，代码短，使我们必须掌握的算法之一。

C++代码：

void floyd(){
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				g[i][j] = min((g[i][k])+g[k][j],g[i][j]);
}

扩展阅读-原理

Floyd是基于动态规划的多源最短路的算法。

定义 $f[k][i][j]$ 为经过前k个结点，从 i 到 j 的最短路径：

$f[k][i][j]$ 可以从 $f[k-1][i][j]$ 转移过来，即不经过第k个节点。
也可以从 $f[k-1][i][k]$ $+f[k-1][k][j]$ 转移过来，即经过第k个节点。

综上，转移方程为 $f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])$ 。我们观察上述转移方程，在更新f[k]层状态的时候，只用到了f[k-1]层的值，f[k-2]及之前的层的值都用不上了。可以用滚动数组进行优化，最终方程为 $f[i][j]=min(f[i][j],f[i][k]+f[k][j])$ 。

蓝桥公园

题目描述

小明喜欢观景，于是今天他来到了蓝桥公园。已知公园有N个景点，景点和景点之间一共有M条道路。小明有Q个观景计划，每个计划包含一个起点st和一个终点ed，表示他想从st去到ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他嘛？

输入描述

输入第一行包含三个正整数N, M, Q

第2到M+1行每行包含三个正整数u，v，w，表示u↔v之间存在一条距离为w的路。

第M+2到M+Q-1行每行包含两个正整数st，ed，其含义为计划起点和终点。

$1\leq N\leq 400,1\leq M\leq\frac{N\times (N-1)}{2},Q\leq 10^3,1\leq u,v,st,ed\leq N,1\leq w\leq 10^9$

输出描述

输出共Q行，对应输入数据中的查询（任意两点最短路）。若无法从st到达ed则输出-1。

输入输出样例

输入

输出

1
3
2

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	3s	128M
Java	2s	128M

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 4e2+10;
typedef long long LL;
int n, m, q;
LL g[N][N];

void floyd(){
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				g[i][j] = min(g[i][k]+g[k][j], g[i][j]);
}

int main(){
	cin >> n >> m >> q;
	memset(g, 0x3f, sizeof g);
	
	while(m--){
		LL a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	
	//初始化自身0
	for(int i = 1; i <=n; i++)
		g[i][i] = 0;
		
	floyd();
	
	while(q--){
		int st, ed;
		cin >> st >> ed;
		cout << (g[st][ed]==0x3f3f3f3f3f3f3f3f?-1:g[st][ed])<<endl;
	}

	return 0;
}