本文主要是介绍最短路径的求法（SPFA,dijkstra），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
关于SPFA
算法大致流程是用一个队列来进行维护。
初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，
如果该点没有在队列中，则将其入队。 直到队列为空时算法结束。
判断有无负环：如果某个点进入队列的次数超过V次则存在负环
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
struct node{int to,v;
};
vector<node>d[maxn];
queue<int>q;
int ans[maxn];
int n,m,s,u,v,w;
bool vis[maxn];
void spfa(){memset(ans,0x3f,sizeof(ans));ans[s]=0;q.push(s);vis[s]=true;while(!q.empty()){int now=q.front();q.pop();for(int i=0;i<d[now].size();i++){int next=d[now][i].to;if(ans[now]+d[now][i].v<ans[next]){ans[next]=ans[now]+d[now][i].v;if(!vis[next]){vis[next]=true;q.push(next);}}}vis[now]=false;}for(int i=1;i<=n;i++){if(ans[i]==0x3f3f3f3f)printf("2147483647 ");else printf("%d ",ans[i]);}
}
int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);d[u].push_back({v,w});}spfa();return 0;
}
虽然在大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度为O(nm) ， 将其卡到这个复杂度也是不难的，所以考试时要谨慎使用（在没有负权边时最好使用 Dijkstra 算法）
关于dijkstra
1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。
2.u标记为已确定最短路径
3.更新与u相连的每个未确定最短路径的顶点v
优先队列优化后，时间复杂度为O(mlogm)
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{int to,v;bool operator < (const node &x)const{return x.v<v;}
};
vector<node>d[maxn];
priority_queue<node>q;
int n,m,s,u,v,to,ans[maxn];
bool vis[maxn];
void dij(){memset(ans,0x3f,sizeof ans);ans[s]=0;q.push({s,0});while(!q.empty()){node now=q.top();q.pop();if(vis[now.to])continue;vis[now.to]=true;for(int i=0;i<d[now.to].size();i++){node next=d[now.to][i];if(ans[next.to]>ans[now.to]+next.v){ans[next.to]=ans[now.to]+next.v;q.push({next.to,ans[next.to]});}}}for(int i=1;i<=n;i++){printf("%d ",ans[i]);}
}
int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&to);d[u].push_back({v,to});}dij();return 0;
}
一个要注意的地方
重载运算符时，我们用了这种方法：
bool operator < (const node &x)const
{return x.v<v;
}
实际上等同于这样
bool operator < (const node &x)const
{return v > x.v;
}
也能写成这样的形式
friend const bool operator <(node x,node y){return x.v>y.v;
}
我们会发现，这实际上是反过来的，有人给出的解释是这样的：
c++ STL 里面都是重载小于号，然后 STL 的优先队列默认是大根堆而不是小根堆，所以只能反着重载运算符
这个地方是要注意的
这篇关于最短路径的求法（SPFA,dijkstra）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
