【算法-图论基础】最短路径-弗洛伊德算法
【算法-图论基础】最短路径-弗洛伊德算法
在生活中，我们往往会遇到这样的问题，从地点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] 
