多源最短路问题
-
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;
}