最短路总结（dijkstra,floyd,bellman,spfa）

1.dijkstra算法

dijkstra算法是基于贪心思想的单源有权最短路算法，用来计算从一个顶点到其余个顶点的最短路算法（边权值都必须为正数）。如果边权值有负数则需要弗洛伊德算法。

具体思路：1.初始时，所有点都在集合内，标记数组vis=0，存值数组d[s]=0，s为起始点，d[其他点]=正无穷

2.从集合内选一个距离最小的点 u，对它进行标记移除集合

3.对 u的所有出边进行松弛操作（即更新邻点 v的最小距离）

4.重复2，3操作，直到圈内为空。

时间复杂度为O(n^2)

#include<bits/stdc++.h> //dijkstra算法 
using namespace std;
#define ll long long
const int N=1e5+10;
typedef struct per{int v,w;
}stu;
int n,m;
vector<stu> q[N];
int d[N],vis[N]; //d数组为从原点到其他点的权值
void dij(int s){for(int i=0;i<=n;i++)d[i]=INT_MAX;d[s]=0;for(int i=1;i<=n;i++){ //枚举次数int u=0;for(int j=1;j<=n;j++) //枚举节点if(!vis[j]&&d[j]<d[u]) //找距离原点最近的点u=j; //将这个点赋值给uvis[u]=1; //标记 u出圈for(auto ed:q[u]){ //枚举与 u相连的节点int v=ed.v,w=ed.w; // v是与 u相连的节点if(d[v]>d[u]+w) //如果从起点到u，再到v，比从起点直接到v更近就更新d[v]的值d[v]=d[u]+w;}}
}
int main(){int s,a,b,c;cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>a>>b>>c;q[a].push_back({b,c});}dij(s);for(int i=1;i<=n;i++)cout<<d[i]<<' ';  //从起点s到节点i 的最短路径 
}

有一个板子题供大家练习

例题链接

视频讲解

2.堆优化

用优先队列维护被更新的点的集合，创建一个pair类型的大根堆 q{-距离，节点}（优先队列），把距离取负值，距离最小的元素最大，一定在堆顶。

1.初始化，{0，s}入队，d[s]=0，d[其他点]= 正无穷

2.从队头弹出距离最小的点 u，若u扩展过则跳过，否则打标记

3.对 u的所有出边执行松弛操作，把{-d[v]，v}压入队尾

4.重复2，3步操作，直到队列为空

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef struct per{int v,w;
}stu;
const int N=1e5+10;
int d[N],vis[N];
vector<stu> q[N];
priority_queue<pair<int,int> > p; //大根堆，我们用的pair用小根堆会写很多
int m,n;
void dij(int s){for(int i=0;i<=n;i++)d[i]=INT_MAX;d[s]=0;p.push({0,s});while(p.size()){auto t=p.top(); //弹出距离原点最小的点p.pop();int u=t.se;if(vis[u]) continue; //如果这个点扩展过就跳过vis[u]=1; for(auto ed:q[u]){int v=ed.v,w=ed.w;if(d[v]>d[u]+w){d[v]=d[u]+w;p.push({-d[v],v}); //因为我们用的大根堆，取负之后，原来小的就会在前面}}}
}
int main(){int a,b,c,s;cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>a>>b>>c;q[a].push_back({b,c});}dij(s);for(int i=1;i<=n;i++)cout<<d[i]<<' ';
}

如果不用堆优化是过不了这题的：

例题链接

解释一下dijkstra算法为什么不能用于有负权的边的图：

因为Dijkstra算法是通过当前离起点最近的点来更新其他的点的距离，例如上图中的 4 号结点会被 2 号结点更新为2+1=3，但实际上4号结点的最短路径是3+(-2)=1，这样你就知道为什么Dijkstra算法不能用于有负权的边的图吧。

2.弗洛伊德算法（Floyd)

弗洛伊德算法既适用于无向加权图，也适用于有向加权图。Floyd算法又称为插点法，是一种利用 动态规划 的思想，寻找给定的加权图中 任意两点之间的最短路径 的算法。

其实就是进行 n次dijstra算法，floyd稠密图效果最佳，它能可以正确处理 有向图 或 无向图 或 负权(但不可存在负权回路) 的最短路径问题，同时也被用于计算有向图的传递闭包。

初始化：

（1）i != j，无边则d[i] [j]=无穷，有边则d[i] [j]=w

（2）i = j，d[i] [j]=0

状态计算：路径的选择分为两类

（1）路径不经过 k点，继承原值

（2）路径经过 k点，松弛操作：d[j] [k]=d[j] [i]+d[i] [k]

有一个板子题供大家练习：例题链接

#include<bits/stdc++.h> //floyd 
using namespace std;
const int N=1100;
int d[N][N],path[N][N]; //d数组存的从i到j的距离，path为路径
int main(){int u,v,n,m,w;  //u代表起始点结，v代表终止结点，w代表边权 cin>>n>>m; //结点个数，边的条数 for(int i=1;i<n+10;i++){for(int j=1;j<m+10;j++){d[i][j]=10000; //距离矩阵初始化，假设代表无穷大 d[i][i]=0; //自己到自己 }}for(int i=1;i<=m;i++){cin>>u>>v>>w;d[u][v]=min(d[u][v],w);d[v][u]=min(d[v][u],w); //无向图相互存储，取min防止有重边覆盖} for(int k=1;k<=n;k++){ //每次选一个 i结点作为中间点 for(int i=1;i<=n;i++){ // j结点作为起始点 for(int j=1;j<=n;j++){ // k结点作为终点 if(d[i][k]+d[k][j]<d[i][j]){ //如果从中间点到达比直接到达更小的话 d[i][j]=d[i][k]+d[k][j]; //更新距离矩阵 path[i][j]=k; //更新路径矩阵，记录插点 }}}}for(int i=1;i<=n;i++){  //距离矩阵 for(int j=1;j<=n;j++)cout<<d[i][j]<<' ';cout<<endl;}
}

下面有一个模拟过程，方便大家理解。只有经过中间点的路径才会被改变。中间点的遍历是不能放在里面的

2.1路径的记录与递归输出

如果我们想要知道两个节点之间的路径，我们可以进行递归输出。

void pa(int i,int j){if(path[i][j]==0) return ;int k=path[i][j];pa(i,k);cout<<k<<' ';pa(k,j);
}

视频讲解1

视频讲解

3.贝尔曼—福特（Bellman-Ford）算法

基于松弛操作的单源最短路算法，也可以处理负边权。时间复杂度为O(n*m)

1.初始化，d[s]=0，d[其他点]=正无穷

2.执行多轮循环，每轮循环，对所有边都尝试进行一次松弛操作

3.当一轮循环中没有成功的松弛操作时，算法停止

如果第 n轮循环时仍然存在能松弛的边，说明从 s点出发，能够抵达一个负环（一条边权之和为负数的回路）。算法可以判断负环。

#include<bits/stdc++.h> //Bell算法 
using namespace std;
#define ll long long
const int N=1e5+10;
typedef struct per{int v,w;
}stu;
int n,m;
vector<stu> q[N];
int d[N]; //d数组为从原点到其他点的权值
bool bell(int s){memset(d,INT_MAX,sizeof d); //初始值为正无穷d[s]=0;bool f;for(int i=1;i<=n;i++){ //枚举次数f=0;for(int u=1;u<=n;u++){ //枚举每个点 if(d[u]==INT_MAX) continue; //如果没有进行过松弛 for(auto ed:q[u]){ //枚举与 u相连的节点int v=ed.v,w=ed.w; // v是与 u相连的节点if(d[v]>d[u]+w){ //如果从起点到u，再到v，比从起点直接到v更近就更新d[v]的值d[v]=d[u]+w;f=1;} }}if(!f) break; //说明这一轮有更新，就退出 }return f;
}
int main(){int s,a,b,c;cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>a>>b>>c;q[a].push_back({b,c});}bell(s);for(int i=1;i<=n;i++)cout<<d[i]<<' ';  //从起点s到节点i 的最短路径 
}

下面有一张图，方便大家理解，假设3是起点，当i=1，u=1时，此时d[u]=INT_MAX，没有被更新所以直接跳过，直到循环到3，对它的邻点进行松弛操作。

视频讲解

4.Bellman-Ford算法的优化——SPFA

只有本轮被更新的点，其出边才有可能引起下一轮的松弛操作，因此用队列来维护被更新的点的集合。最坏情况为O(n*m)

1.初始化，s入队，标记s在队内，d[s]=0，d[其他点]=正无穷

2.从队头弹出 u点，标记 u不在队内

3.枚举 u的所有出边，执行松弛操作。记录从 s走到 v的边数，并判负环。如果不在队内则把 v压入队尾，并打上标记。

4.重复2，3步操作，直到队列为空

#include<bits/stdc++.h> //spfa算法 
using namespace std;
#define ll long long
const int N=1e5+10;
typedef struct per{int v,w;
}stu;
int n,m;
vector<stu> q[N];
queue<int> p;
int d[N],vis[N],cnt[N]; //d数组为从原点到其他点的权值
bool spfa(int s){memset(d,INT_MAX,sizeof d);d[s]=0;vis[s]=1;p.push(s);while(p.size()){int u=p.front();p.pop();vis[u]=0; //只有不在队内才入队 for(auto ed:q[u]){int v=ed.v,w=ed.w;if(d[v]>d[u]+w){d[v]=d[u]+w;cnt[v]=cnt[u]+1; //记录从 u点走到 v点的边数 if(cnt[v]>=n) return 1; //说明已经走到一个负环了 if(!vis[v]){p.push(v);vis[v]=1; //进行入队 }}}}return 0;
}
int main(){int s,a,b,c;cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>a>>b>>c;q[a].push_back({b,c});}spfa(s);for(int i=1;i<=n;i++)cout<<d[i]<<' ';  
}

下面有个例子：

先对1进行出队操作，因为刚开始1进行了入队，接下来对1的邻边进行松弛操作，再把1的邻边{3，2}进行入队，接着3出队，对3的邻边进行松弛操作（因为3进行了松弛操作，3距离原点的距离变得更小了，那么就需要让进行过松弛操作的点的邻边入队且邻边不在队中）。

4.1 SPFA判断负环

什么是负环呢？ 下图左边的2——>3——>4就是一个负环，因为转一圈后的距离是负的，右图的 1 结点是自环，也属于负环。

相比上一个代码，多了一个cnt数组，cnt[x] 代表起点到x最短路所经的边数，当 cnt[x] ≥ n 时，则说明 1——>x 这条路径上至少经过 n 条边 ，那么也就是 1——>x 这条路径上至少经过 n+1 个点，而我们知道总共只有 n 个点，说明至少存在两个点是重复经过的，那么这个点构成的环一定是负环，因为只有负环才会让dist距离变小，否则我们为什么要两次经过同一个点呢。

有一道判断负环的板子题：例题链接

#include<bits/stdc++.h> //spfa算法 
using namespace std;
#define ll long long
const int N=5010;
typedef struct per{int v,w;
}stu;
int n,m;
vector<stu> q[N];
queue<int> p;
int d[N],pre[N],vis[N],cnt[N]; //d数组为从原点到其他点的权值
bool spfa(int s){memset(d,0x3f,sizeof d); //更新为INT_MAX会出错memset(cnt,0,sizeof cnt);memset(vis,0,sizeof vis);d[s]=0;vis[s]=1;p.push(s);while(p.size()){int u=p.front();p.pop();vis[u]=0; //只有不在队内才入队 for(auto ed:q[u]){int v=ed.v,w=ed.w;if(d[v]>d[u]+w){d[v]=d[u]+w;pre[v]=u; //记录前驱点 cnt[v]=cnt[u]+1; //记录从 u点走到 v点的边数 if(cnt[v]>=n) return 1; //说明已经走到一个负环了 if(!vis[v]){p.push(v);vis[v]=1; //进行入队 }}}}return 0;
}
int main(){int s,a,b,c;int t;cin>>t;while(t--){for(int i=0;i<=N;i++) //二维vector进行清除，需要一行一行清除q[i].clear();cin>>n>>m;for(int i=1;i<=m;i++){cin>>a>>b>>c;q[a].push_back({b,c});if(c>=0)q[b].push_back({a,c});}  if(spfa(1))cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}

4.2路径的记录与递归输出

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int N=1e5+10;
typedef struct per{int v,w;
}stu;
int n,m;
vector<stu> q[N];
queue<int> p;
int d[N],pre[N],vis[N],cnt[N]; //d数组为从原点到其他点的权值,pre记录前驱
bool spfa(int s){memset(d,0x3f,sizeof d);d[s]=0;vis[s]=1;p.push(s);while(p.size()){int u=p.front();p.pop();vis[u]=0; //只有不在队内才入队 for(auto ed:q[u]){int v=ed.v,w=ed.w;if(d[v]>d[u]+w){d[v]=d[u]+w;pre[v]=u; //记录前驱点 cnt[v]=cnt[u]+1; //记录从 u点走到 v点的边数 if(cnt[v]>=n) return 1; //说明存在负环if(!vis[v]){p.push(v);vis[v]=1; //进行入队 }}}}return 0; //不存在负环
}
void dfs_path(int u){ //输出路径 if(u==1){cout<<u<<' ';return ;}dfs_path(pre[u]);cout<<u<<' ';
} 
int main(){int s,a,b,c;cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>a>>b>>c;q[a].push_back({b,c});}spfa(s);dfs_path(n);  
}

5.总结

单源最短路：求一个点到其他点的最短路

多源最短路：求任意两个点的最短路

稠密图用邻接矩阵存，稀疏图用邻接表存储。

稠密图：m 和 n^n 一个级别

稀疏图：m 和 n^n 一个级别