- 认为讲得好不妨支持一下
Floyd算法
- 是一种多源最短路算法
- 时间复杂度 $O(n^3)$
1 - 思路
用非常暴力的手段,枚举三个点,
分别是: 断点,出发点,终点 ,
类似动态规划的方法把 出发点到终点 的最短路,
转化为 出发点到断点 与 断点到终点 最短路的和来更新。
步骤
-
预处理,除一个点到自身的最短距离为0以外,到其他点的最短距离都为无穷大;
-
输入边,直接转化为相邻点间的最短路;
-
枚举,更新;
这个枚举更新整个图的过程类似于 动态规划 。
原理
- 注:枚举层次为: $k$ , $i$ , $j$ ,这样保证了更新时用到的值都已确定。
2 - 代码
例题:
最短路
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, k;
int dist[N][N]; //dist[i][j]表示i到j的最短路长度
void Floyd()
{
for (int k = 1; k <= n; k ++) //断点
for (int i = 1; i <= n; i ++) //出发点
for (int j = 1; j <= n; j ++) //终点
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
//初始化,除一个点到自身的距离为0,到其它点的距离都为无穷大
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
//输入边,直接转化为相邻点的最短路
for (int i = 1; i <= m; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
dist[a][b] = min(dist[a][b], c);
}
Floyd();
while (k --)
{
int x, y;
scanf("%d%d", &x, &y);
if (dist[x][y] >= INF / 2) puts("impossible");
else printf("%d\n", dist[x][y]);
}
return 0;
}