【算法】Floyd多源最短路径算法

一、概念

二、思路

三、代码

一、概念

在前面的学习中，我们已经接触了Dijkstra、Bellman-Ford等单源最短路径算法。但首先我们要知道何为单源最短路径，何为多源最短路径

单源最短路径：从图中选取一点，求这个点到图中其他节点的最短路径
多源最短路径：从图中任选两个节点，我们都能知道这两点间的最短路径

Floyd多源最短路径算法可用于求图中任意两点间的最短路径长，其核心思路在于依次将每个节点作为路径的中间点来更新其他任意两点的较优解，最后得到全局最优解

二、思路

1.首先我们需要一个图，和二维数组g、path

其中：

g用于存储从i到j的最短路径长度
path用于存储从i到j的最短路径的终点的前继节点

例如初始时，从1到2的最短路径就是权重为6的边，其终点为2，而对于这条路径而言2的前继节点为1，因此path[1][2] = 1

g(0)和path(0)意为矩阵g和path的初始态。因为初始时两个节点之间的最短路径就是他们之间的边，因此我们在初始化这两个数组时，只需要按照样例输入的边填写矩阵g即可

若从i到j之间没有边，则填最大值即可，例如g[3][2] = MAX，因为没有从3指向2的边

而矩阵path在初始化时按照上面的规则初始化即可，例如初始从3到1的最短路径就是3->1，终点为1，前继节点为3，因此path[3][1] = 3

2. 从1号节点开始，将每个节点作为任意两个节点的最短路径的中间点

有的人听到这里可能已经懵了，我们跟着图慢慢走

此时g(0)、path(0)变为g(1)和path(1)，代表接下来要更新 i->1->j 的最短路径

但是我们并不需要将矩阵g和矩阵path中的所有值都更新，例如g[1][2]，判断1->1->2的路径是否比1->2的最短路径更短是不具有价值的。两个矩阵中，如果行标和中间节点一样、列标和中间节点一样或者行标和列标一样的话，我们直接跳过即可

因此，只有2->1->3的情况，和3->1->2的情况需要讨论

（带虚线的位置代表不需要判断）

可以看到，2->1->3的距离为2->1的最短距离加1->3的最短距离，即g[2][1]+g[1][3] = 23，这个距离并不比g[2][3]小，因此不需要更新

而3->1->2的距离为11，小于原来的值MAX，因此更新，同时path[3][2]也更新为3->1->2的终点的前继节点即1

3.重复第二步直到所有节点都已作为中间点

1->2->3的距离为g[1][2]+g[2][3] = 10，比原来的13更小，因此将g[1][3]更新，path[1][3] = 2

3->2->1的距离为g[3][2]+g[2][1] = 21，比g[3][1]大，不更新

1->3->2的距离为21，比g[1][2]大，不更新

2->3->1的距离为g[2][3]+g[3][1] = 9，比原来的10更小，因此将g[2][1]更新，path[2][1] = 3

至此，我们就得到了图中任意两点间的最短路径长度了

而最短路径本身，则可以根据矩阵path中的值推出来，例如要求从2到1的最短路径，首先知道终点为节点1，根据path[2][1]知道下一个节点3，再根据path[2][3]知道下一个节点2，最后path[2][2]为-1说明路径走到结尾，因此完整的最短路径就为2->3->1

三、代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;

#define N 210
#define M 20010

int n, m, k;
int g[N][N]; //存储从i到j的最短路径长度
int path[N][N] = {-1}; //path[i][j]存储从i到j最短路径的终点 的 前继节点

void Floyd()
{
    for(int i = 1; i <= n; i++)
	{
	    g[i][i] = 0; //自己到自己的路径长度设置为0
	    path[i][i] = -1; //自己到自己的路径设置为-1
	}
	
	for(int k = 1; k <= n; k++) //代表从i经过k到j的最短路径
	{
		for (int i = 1; i <= n; i++) //第i行
		{
			for (int j = 1; j <= n; j++) //第j列
			{
				if(i == j || i == k || j == k) //多余情况
					continue;

				if(g[i][k] + g[k][j] < g[i][j]) //从i经过k到j的最短路径 比 原先从i到j的最短路径更短
				{
					g[i][j] = g[i][k] + g[k][j]; //更新从i到j的最短路径
					path[i][j] = path[k][j]; //更新从i到j最短路径的终点 的 前继节点
				}
			}
		}
	}
}

void solve()
{
    memset(g, 0x3f, sizeof g);
	

	cin >> n >> m >> k;
	for(int i = 0;i < m; i++)
	{
	    int a, b, w;
	    cin >> a >> b >> w;
	    g[a][b] = min(g[a][b], w); //可能存在重边
		path[a][b] = a; //初始时从a到b最短路径终点的前继节点就是a本身
	}

	Floyd(); //Floyd算法

	for (int i = 0; i < k; i++)
	{
		int a, b;
		cin >> a >> b;
		if(g[a][b] > INF / 2)
			cout << "impossible" << endl;
		else
			cout << g[a][b] << endl;
	}
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}

完.