最近再刷2021蓝桥杯真题时刷到一道题，用到了floyd或者dijkstra。这两种都是用来求最短路径问题的。虽然之前学的深度优先算法（DFS）和宽度优先算法（BFS）也能求最短路径，但是时间复杂度太高，并且右很大的局限性。这篇我们先学习Floyd算法
学习Floyd算法请点我
Floyd算是dp的一种应用吧，之前学习的前缀和以及二维前缀和都是dp思想。
佛洛伊德是最简单的最短路径算法，可以计算图中任意两点间的最短路径。时间复杂度为O(N3)，适用于出现负边权的情况。算法描述:
(a)初始化:点u、v如果有边相连，则dis[u][v]=w[u][v]如果不相连，则dis[u][v]=0x3f
(b)for(k=1;k<-n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dis[iljl>dis[i]k]+dis[k]lil)
disli]j]=dis[i][k]+dis k]lil;
(c)算法结束:dis[ili得出的就是任意起点i到任意终点i的最短路径。
疑问:为什么枚举中间点的循环k要放在最外层?
可以从一定不经过k点与一定经过k点的三维数组比较中推导出来
接下来我们看一道题练习一下；
题目描述
有向图的单源点最短路问题
输入格式
第1行:2个空格分开的整数n(2<=n<=500)和m(10<=m<=20000)，分别表示图的顶点数和边数第2.m+1行:每行3个空格分开的整数i，，w。i表示一条边的起点，i表示终点，w表示权值。第m+2行:2个整数s，t1<=s，t<=n)表示指定的顶点。
输出格式
第1行:最小距离
第2行:最短路径(从起点到终点的序列，用1个空格分开)
#include <iostream> #include <cstring> using namespace std; int n,m; int s,t; int div[505][505]; int ans[505][505]; void write(int x){ if(ans[s][x]==0){ return; } write(ans[s][x]); //ans[s][x]，代表s->x最短路线中，x点上一个点的数值，x代表终点 cout<<x<<' '; } int main(){ memset(div,0x3f,sizeof(div)); //为什么时0x3f，int的4个字节都赋值为0x3f，10的9次方量 // 级，可以作为无穷大使用 cin>>n>>m; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; div[a][b]=c; //div[a][b]=c;代表a点连接到b点的距离为c ans[a][b]=a; //ans[a][b]=a代表a到b要经过a点，也就是自己的位置 } cin>>s>>t; for(int i=1;i<=n;i++){ //自己到自己距离为0 div[i][i]=0; } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(div[i][j]>div[j][k]+div[k][i]){ div[i][j]=div[j][k]+div[k][i]; //求每两个点最短距离存储下来 ans[i][j]=ans[j][k]; //一开始i->j,后来i->k->j中间加一个k，当前点移动 //到j } } } } cout<<div[s][t]<<' '<<s<<' '; write(t); //打印路径顶点 return 0; }
