文章目录
前言
一、什么是Floyd算法
二、AcWing 854. Floyd求最短路
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：Floyd，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、什么是Floyd算法
计算最短路算法的一种，相较于Dijkstra，bellman-ford，spfa，Floyd算法是计算多源最短路问题的算法，下图来自AcWing算法基础课：
二、AcWing 854. Floyd求最短路
本博客给出本题截图：
本题分析
dist数组的含义是两点之间的距离，例如dist[i][j]代表的是从i点到j点的距离
这里也同样解释一下为什么写成if (dist[a][b] > INF / 2)
和bellman-ford算法写成这样的原因一致，因为我们存在负权边，所以就算是两个正无穷的边在更新的时候，正无穷和正无穷之间的边权为负，那么另一个正无穷被更新的时候会是正无穷减去一个数，小于INF，故我们直接要求dist[a][b] > INF / 2即可.
算法核心：
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]); }
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 210, INF = 1e9; int dist[N][N]; int n, m, k; 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); 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; while (m -- ) { int x, y, z; scanf("%d%d%d", &x, &y, &z); dist[x][y] = min(dist[x][y], z); } floyd(); while (k -- ) { int a, b; scanf("%d%d", &a, &b); if (dist[a][b] > INF / 2) puts("impossible"); else printf("%d\n", dist[a][b]); } return 0; }
三、时间复杂度
关于Floyd算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
