多源最短路Floyd算法

多源最短路算法-Floyd

使用Floyd（弗洛伊德）算法，可以以 \(O(n^3)\) 的时间复杂度求出一张多源图的任意两点间的最短路径

一般采用邻接矩阵的方法来存储图：

int g[N][N];
g[i][j]

其中，g[i][j]的意义为第i个节点到第j个节点的权重

我们需要对邻接矩阵进行路径初始化，将自身到自身的权重设置为 \(0\) ，到其他节点的距离初始化为 \(+\infty\)（或极大的一个值）

for (int i = 0; i <= N; i++)
	for (int j = 0; j <= N; j++)
		if (i == j) g[i][j] = 0;
		else g[i][j] = 1e9;

对有向图而言，我们通过三个参数进行边的读入：

cin >> u >> v >> w;
g[u][v] = min(g[u][v], w);//判断重边

如果是无向图，则只需要再次赋值反向边即可

g[u][v] = g[v][u] = min(g[u][v], w);

Floyd算法原理：

对任意两个节点a,b而言，如果存在有更短的路径连通它们两个，则必然存在另外一个节点c，使得：

g[a][b] < g[a][c] + g[c][a]

换言之，如果需要更新我们的最短路径，就需要额外的一个中转节点来加入我们的路径中

同样的，如果对经过三个节点的路径a,b,c，能更新一个更短的路径，就需要加入d节点

不难写出以下代码：其中，我们的 i 为新加入的节点

for (int j = 1; j <= N; j++)
	for (int k = 1; k <= N; k++)
		g[j][k] = min(g[j][k], g[j][i] + g[i][k]);

每次遍历两层所有节点，目的是更新每个节点间的最短路径，并判断能否通过新加入的 i 节点，得到一个更短路径

我们的 i节点可以取到所有的节点来作为路径中转
因为相对于任意两个节点，我们都能够使用其余的节点来构建出一条经过任意多的中转节点的最短路径

于是有最终的递推函数，求得最短路：

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

注意：Floyd算法不能对存在负环的图使用，如果存在负环，每次取路径的min时，都会取到更小的负数，导致无法正确退出循环

以洛谷B3647为例：

输出最终的邻接矩阵

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int g[105][105];

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

int main()
{
	cin >> n >> m;
	int u, v, w;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			if (i != j) g[i][j] = 1e9;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = min(g[u][v], w);
	}
	floyd();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << g[i][j] << ' ';
		cout << endl;
	}
	return 0;
}