【图论】最短路（一）

发现之前做的题很乱，用小笔记把看过的博客和题目分类记录一下，

代码参考了很多佬，是标注出来的链接，若不同意我就删掉（鞠躬）

找了几张好点的，图来源图中的id和acwing

1.dijkstra     依次找到距离集合最近的点加入集合

1.1朴素dijkstra

估计也用的少，见3.1 模板最短路x2

1.2堆优化版dijkstra

当点/边数目达10^5时，用了才能在1s内

void dijkstra(){
priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> heap;
heap.push({0,s});
dist[s]=0;while(!heap.empty()){pair<long long ,long long>temp=heap.top();heap.pop();long long x=temp.first;long long y=temp.second;if(st[y])continue;st[y]=true;for(long long i=head[y];i!=-1;i=edge[i].next){//边的编号ilong long t=edge[i].to;if(dist[t]>x+edge[i].w){dist[t]=x+edge[i].w;heap.push({dist[t],t});}}}}

2.bellman-ford      经过n-1轮对每条边进行松弛

最短路问题 Bellman-Ford（单源最短路径）(图解)_bellmanford算法图解-CSDN博客

2.1 bellman-ford

void bellman(){
for(int i=2;i<=n;i++)dist[i]=INF;dist[1]=0;for(int i=1;i<=n-1;i++){bool ok=1;for(int j=1;j<=tot;j++){int u=edge[j].u;int v=edge[j].v;if(dist[u]!=INF&&dist[v]>dist[u]+edge[j].w){//dis[u]!=INF很是重要dist[v]=dist[u]+edge[j].w;ok=0;}}if(ok==1)break;}}

2.2 spfa 队列优化的

注意vis[u]=false;

void spfa(int s){for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=false;
queue <int> q;
q.push(s);
dis[s]=0,vis[s]=true;while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;if(!vis[v]){q.push(v);vis[v]=true;cnt[v]++;
}}}}}