【算法-图论基础】最短路径-弗洛伊德算法

【算法-图论基础】最短路径-弗洛伊德算法

在生活中，我们往往会遇到这样的问题，从地点A到地点B，选择什么线路，选用哪几种交通工具的组合，花费的时间最少？

这个问题中，我们可以借助欧拉使用的数学工具——图论来研究，我们将每一个地点抽象为点，道路或者一个阶段的过程抽象为边，花费的时间就是边的权值。这样，问题就简化为在一个图中找两点之间的最短路径。

怎样解决这个问题呢，罗伯特·弗洛伊德给出了答案。

弗洛伊德算法采用动态规划的思想，假设我们要找的最短路径在点A与点B之间，那么，图中的所有点只有两种情况，要么在这条最短路径上（也就是中间点），要么不在这条最短路径上，我们可以根据这个来得出状态转移方程，依次将图中的每个点作为中间点遍历即可。

下面的题目来自蓝桥题库：

输入输出样例

输入：

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3

输出：

1
3
2

按照题目意思我们可以得到下图：

此时，我们只考虑边权值为正。

在弗洛伊德算法中，我们采用邻接矩阵存图，因为这是天然的dp数组（两点之间无连接则值记为无穷大，方便找最小值），同时，为了能够得到最短路径我们用 f [ x ] [ y ] f[x][y] f[x][y]来记录从x到y的最短路径（保存y的前一个点）。

我们考虑图中的每一个点。

1、当点1作为中间点时（A->…->1->…->B）

更新两个数组， d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ 1 ] + d p [ 1 ] [ j ] ) dp[i][j] = min(dp[i][j], dp[i][1] + dp[1][j]) dp[i][j]=min(dp[i][j],dp[i][1]+dp[1][j]) ，如果 d p [ i ] [ j ] = d p [ i ] [ 1 ] + d p [ 1 ] [ j ] dp[i][j]=dp[i][1]+dp[1][j] dp[i][j]=dp[i][1]+dp[1][j]，对应 f [ i ] [ j ] = f [ 1 ] [ j ] f[i][j]=f[1][j] f[i][j]=f[1][j]（注意只能取后半段）。

在本题的环境下，很显然，绿色部分是不用更新的，保留即可。

本轮不必更新，保留。

2、当点2作为中间点时（A->…->2->…->B）

黄色部分需要更新。

3、当点3作为中间点时（A->…->3->…->B）

本轮不必更新，保留。

遍历结束，得到最终结果。

再用查表的方法就能得到两点之间的最短路径值。

那么如何得到两点间的最短路径呢？

；利用f数组，我们知道A到B的最短路径中，B的前驱点是 f [ A ] [ B ] f[A][B] f[A][B]，即 A − > . . . − > f [ A ] [ B ] − > B A->...->f[A][B]->B A−>...−>f[A][B]−>B，我们再将 f [ A ] [ B ] f[A][B] f[A][B]看作是 B B B，一直向前倒推即可。

AC代码放在下面：

#include
using namespace std;
#define int long long
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, q;
int a[N][N];
void init() {
	for (int i = 1; i 
		for (int j = 1; j 
			if (i != j) a[i][j] = INF;
		}
	}
	return;
}
void floyd() {
	for (int i = 1; i 
		for (int j = 1; j 
			if (j == i) continue;
			for (int k = 1; k 
				if (k == j || k == i) continue; // 跳过对角线
				if (a[j][k]  a[j][i] + a[i][k]) {
					a[j][k] = a[j][i] + a[i][k];
				} // 更新最短路径长度及最短路径
			}
		}
	}
	return;
}
signed main() {
	cin  n  m >> q;
	init();
	for (int i = 1; i 
		int from, to, value;
		cin > from >> to >> value;
		a[from][to] = a[to][from] = min(a[from][to],value);
	} // 邻接矩阵存图
	floyd();
	while (q--) {
		int f, t;
		cin >> f >> t;
		if(a[f][t]