最短路算法1 Floyd

· · 个人记录

你一定听过下面这句话：

关于Floyd，他太慢了

关于SPFA，他死了

关于dijkstra,就选他吧

这些你看不懂的英文字母就是最短路里面的算法

什么是最短路问题

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径（从CSDN抄来的比较专业说白了其实就是一个图让你求一个点到另一个点的最短距离）

那么今天来讲一讲最短路最简单但是最低效的算法：

Floyd

这种算法是解决任意两点间的最短路径的一种算法，比如有两个点i,j和一个中介点k我要计算i到j的距离和i到k加上k到j的距离哪个短，这就是floyd的思想。

其实实质上是比较简单的dp（动态规划），枚举阶段状态决策，但是这种算法特殊的是他的决策放在上面

定义f数组f[i][j]：代表i到j的距离 （其实这就是dp里的第一步，搞清楚f数组的含义）

然后枚举即可，代码实现如下：

#include<bits/stdc++h>
using namesapce std;
int f[10001][10001],n;
int main(){
    cin>>n;
    for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(f[i][j]>f[i][k]+f[j][k])
                        f[i][j]=f[i][k]+f[j][k];
 }

很显然时间复杂度为O(n³)，只能用来计算一些小规模的水题

所以就会有

关于Floyd，它太慢了

这句话了

（本篇仅用来作者本人复习，写的不好的大佬骂轻点）