• Floyd算法

例题

【模板】Floyd 算法

原理

Floyd 算法的思想是动态规划。维护一个数组 dis[k][u][v] ，表示从点 \(u\) 到点 \(v\) 的最短路径，且中间经过的点（不包括 \(u\), \(v\) ）的序号最大为 \(k\)。

状态转移方程:

\(f(k,u,v) = min{(f(k-1,u,v),f(k-1,u,k)+f(k-1,k,v))}\)

为了节省空间开销，我们可以压掉第一维，简化后的状态转移方程即为：

dis[1][u][v] = min(dis[0][u][v], dis[0][u][k] + dis[0][k][v])

代码

//多源最短路问题
//Floyd算法
#include <iostream>
using namespace std;
int n, m;//表示点的个数和边的个数
int e[105][105];
int dis[2][105][105];//dis[i][u][v]表示u->v的最短路径
void init()
{
	cin >> n >> m;
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)e[i][j] = 10000000;
	}
	for (int i = 1; i <= n; i++)e[i][i] = 0;
	for (int x = 0; x <= 1; x++)
	{
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= n; j++)dis[x][i][j] = 10000000;
		}
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e[u][v] = e[v][u] = w;//邻接矩阵存图
	}
}
void Floyd()
{
	//状态转移方程dis[k][u][v] = min(dis[k - 1][u][v], dis[k - 1][u][k] + dis[k - 1][k][v]);
	//但是第一维可以压掉，变成dis[1][u][v] = min(dis[0][u][v], dis[0][u][k] + dis[0][k][v])，让空间复杂度从n*n*n降低到n*n
	for (int u = 1; u <= n; u++)
	{
		for (int v = 1; v <= n; v++)
		{
			dis[0][u][v] = e[u][v];//初始状态
		}
	}
	
	for (int k = 1; k <= n; k++)
	{
		for (int u = 1; u <= n; u++)
		{
			for (int v = 1; v <= n; v++)
			{
				dis[k & 1][u][v] = min(dis[(k - 1) & 1][u][v], dis[(k - 1) & 1][u][k] + dis[(k - 1) & 1][k][v]);
			}
		}
	}
}
void output()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)cout << dis[n & 1][i][j] << " ";
		cout << endl;
	}
}
int main()
{
	init();
	Floyd();
	output();
	return 0;
}