SPFA,Dijkstra与Floyd
2025-06-07 20:46:14
发布于：上海
阅前说明:
单源最短路与多源最短路:
单源最短路:求从一个固定起点出发,到图中任意顶点的最短距离.
多元最短路:求从任意起点出发,到图中任意顶点的最短路距离.
*当然,求单源最短路的算法重复执行n次(n是总顶点个数)就是多源最短路算法.而多源最短路算法在无时间限制的情况下,也可以用作单源最短路算法
松弛: 最短路的核心思想.
操作方式:以某一个顶点作为中转站,更新与这个顶点相邻的其他顶点的数值
(这种操作称为对中转站顶点的松弛)
(上述说法选自Yuilice老师的最短路算法,这里会配图更详细的解释这个说法)
比如这张无向图(标明的数字是路径长度):
现已知想要从点A走到点D有一条路:A -> C -> D (路径长度:25)
那现在取点B作为中转站进行松弛,发现:
A -> B ->D 这条路径长度为22.
那么就将点A到点D的最短距离更新为22
一.Dijkstra
最短路算法的一种,单源最短路算法,基于贪心思想.但同样,其缺点也因贪心思想而诞生.
其主要过程:不断挑选与起始点距离最近的点,并利用挑选到的点与其他顶点进行松弛.(每个点只会被挑选一次)
贪心思想的体现:挑选与起始点"距离最近的点"
贪心思想带来的缺点:无法处理负权便
可以使用堆优化时间复杂度:在挑选与起点距离最近的点时,利用优先队列"priority_queue"
时间复杂度:
代码:
#include<bits/stdc++.h>
using namespace std;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
bool vis[100005];
int dis[100005];
vector<Node>v[100005];
priority_queue<Node>q;
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
}
for(int i=0;i<=n+1;i++){
dis[i]=1e9;
}
dis[s]=0;
q.push({s,0});
while(!q.empty()){
Node sum=q.top();
q.pop();
int k=sum.z;
if(!vis[k])vis[k]=1;
else continue;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
q.push({to,dis[to]});
}
}
}
for(int i=1;i<=n;i++){
if(i!=1)cout<<" ";
cout<<dis[i];
}
return 0;
}
二.SPFA
最短路算法的一种,单源最短路算法,铃铛人的优化.与DIJ不同,SPFA的松弛从边入手,将每次产生了变化的边的点放入队列.
也因此,SPFA与DIJ不同,它可以解决负权边,也可以判断负环.
优化:相比于Bellman,SPFA不会对没有发生变化的边进行无意义的松弛(取自Yuilice老师的最短路算法
判断负环:SPFA中,一个点不会被加入队列超过(>=)n次.
例题:T18691.小码君的太空基地【SPFA】
#include<bits/stdc++.h>
using namespace std;
struct Node{
int z,q;
};
vector<Node>v[100005];
int dis[100005];
bool vis[100005];
queue<int>q;
int main(){
int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
}
for(int i=0;i<=n+1;i++){
dis[i]=1e9;
}
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int k=q.front();
q.pop();
vis[k]=0;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to]){
vis[to]=1;
q.push(to);
}
}
}
}
cout<<dis[t];
return 0;
}
补充:注意到SPFA和Dijkstra都有一个叫vis的数组(从个人角度来说,我认为SPFA和Dijkstra的代码长得还是挺像的,所以要注意区分.)不同点在于,SPFA的vis[i]代表的是i这个顶点是否在队列中;而Dijkstra的vis[i]代表的是i这个顶点有没有松弛过.
三.Floyd
最短路算法的一种,相对于SPFA和Dijkstra来说,是多源最短路算法.和动态规划有异曲同工之妙.
优点在于代码简单易写易理解.缺点在于时间复杂度高达
操作方式:三层循环,第一层循环枚举松弛顶点,第二层循环枚举起点,第三层循环枚举终点.
例题:A29680.最短距离查询【Floyd】
智慧代码:
#include<bits/stdc++.h>
using namespace std;
int a[205][205];
int dis[205][205];
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=1e9;
}
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=z;
dis[x][y]=z;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
dis[x][y]==1e9 ? cout<<"impossible"<<'\n' : cout<<dis[x][y]<<'\n';
}
return 0;
}
*本篇学习讨论部分内容基于Yuilice老师的最短路算法 嗷嗷嗷嗷嗷窝最短路算法梦开始的地方,预习的时候就逮着这篇疯狂学 感谢老师
并且感谢 BaiRX 同学提出的 这篇学习讨论的漏洞 万分感谢!(●'◡'●)
有帮助，赞一个