一、最短路问题

1、对于稠密图，由于朴素版的dijkstra算法与边数无关使用这种算法的复杂度较低。稀疏图用堆优化版的算法；单源最短路中存在负权边用SPFA 算法通常较好；多源用floyd算法；

 难点：如何建图，抽象为最短路问题。

二、朴素版dijkstra算法

由于稠密图用这种算法，邻接矩阵存图，注意把g初始化为0x3f；st保存每个数组的状态，

#include<bits/stdc++.h>
//849dijkstra最短路
using namespace std;
const int N=510;
int g[N][N],disk[N],st[N];
int n,m;
int dijkstra()
{disk[1]=0;for(int i=1;i<=n;i++){int t=-1;//找最小的那个for(int j=1;j<=n;j++)if(st[j]==-1&&(disk[t]>disk[j]||t==-1))t=j;st[t]=1;//标记for(int j=1;j<=n;j++)disk[j]=min(disk[j],disk[t]+g[t][j]);}if(disk[n]==0x3f3f3f3f)return -1;return disk[n];
}
int main()
{cin>>n>>m;memset(disk,0x3f,sizeof disk);//初始化最短路为正无穷memset(g,0x3f,sizeof g);memset(st,-1,sizeof st);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;//由于存在重复带权边，所以要留住那个较短的边因此初始化g为无穷g[a][b]=min(g[a][b],c);}int t=dijkstra();cout<<t<<endl;return 0;
}

三、堆优化版的dijkstra算法

在获取disk最小的节点的位置进行优化。用堆来存储起点到目标节点的距离。又因为算法每次更新边，更新一次堆的时间复杂度为log(n),时间复杂为O(m log(n))

直接使用优先队列实现堆，优先队列中的元素为pair元素，first为路径长度，second为端点名字。

#include<bits/stdc++.h>
//850dijkstra最短路（堆优化）邻接表存图
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int h[N],e[N],ne[N],idx,w[N];
int disk[N],st[N];
int n,m;
void add(int a,int b,int c)//将边和权重保存到邻接表中
{e[idx]=b;ne[idx]=h[a];w[idx]=c,h[a]=idx++;
}
int dijkstra()
{disk[1]=0;priority_queue<PII,vector<PII>,greater<PII>>heap;//小顶堆heap.push({0,1});while(heap.size()){auto t=heap.top();//拿出堆顶heap.pop();int ver=t.second,distance=t.first;if(st[ver]==1) continue;//已经确定过最短路继续st[ver]=1;for(int i=h[ver];i!=-1;i=ne[i])//遍历与其相连的所有边{int j=e[i];if(disk[j]>distance+w[i]){//更新后的disk可能不是最小值//这些没有用的中间值即使跑到堆顶取出来了//但是只要发现对应的点已经确定最短路了就放弃disk[j]=distance+w[i];heap.push({disk[j],j});}}}if(disk[n]==0x3f3f3f3f)return -1;return disk[n];
}
int main()
{cin>>n>>m;memset(disk,0x3f,sizeof disk);//初始化最短路为正无穷memset(st,-1,sizeof st);memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);}int t=dijkstra();cout<<t<<endl;return 0;
}

三、  Bellman_Ford算法（用于求有边数限制的最短路）

可以用于用来找负环，或者有最多经过k条边的限制的题目。

而且即使有负环让你求最短路，有k条边的限制也不会出现负无穷的结果

算法：进行指定次数的循环，每次循环都遍历所有边

#include<bits/stdc++.h>
// 853. 有边数限制的最短路 (bellman_ford)
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct Edege//结构体保存边，便于遍历
{int a,b,c;
}edges[M];int bellman_ford()
{memset(dist,0x3f,sizeof dist);//初始化dist[1]=0;for(int i=0;i<k;i++){memcpy(backup,dist,sizeof dist);//复制上一次的结果到backup，//防止发生串性地更新for(int i=0;i<m;i++){int a=edges[i].a,b=edges[i].b,w=edges[i].c;dist[b]=min(dist[b],backup[a]+w);}}//由于存在负边，可能会小于0x3f3f3f3f,根据题目的数据范围，计算最多减的次数if(dist[n]>=0x3f3f3f3f/2)return -1;else return dist[n];
}
int main()
{cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,w;cin>>a>>b>>w;edges[i]={a,b,w};//保存边}int t=bellman_ford();if(t==-1)puts("impossible");else cout<<t<<endl;return 0;}

四、SPFA算法求最短路

SPFA算法其实就是在Bellman-ford算法基础上的优化。Bellman-ford算法看起来比较傻，每次迭代的话是遍历所有边来更新，但是每次迭代的话不是每条边都会更新。SPFA算法就是对这个做优化，每次迭代dist[b]可以更新的话，一定是dist[a]变小了，因为如果dist[a]不变的话，dist[b]一定不变。只有dist[a]变小了，它的后继才会变小。所以SPFA算法就从这个点进行优化。

SPFA算法的思路就是迭代的时候用一个队列来做，队列里面存的就是到起点距离变小的点。先把起点放到队列里面去，只要队列不空，也就是队列里面还有距离变小的点的话，就执行一下操作：

先取出队头t，然后队头出队
更新t的所有出边，t到起点的距离不是变小了吗， 那么所有和t相连的点都有可能变小，如果更新成功的话，就入队。但是注意要判断一下这个点已经入过队的话就不用重复加入了。

————————————————           
原文链接：https://blog.csdn.net/qq_52905520/article/details/126574584

例题：利用spfa算法求最短路，从队列头拿出结点，只要能更新就更新，并把更新的点加入到队列中，并利用st bool数组保存队列中是否已经有当前结点。

spfa算法中不使用backup的原因是每次更新只更新邻边，不会出现串联更新。

#include<bits/stdc++.h>
//
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx,w[N];
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;}
int spfa()
{memset(dist,0x3f,sizeof dist);memset(st,false,sizeof st);dist[1]=0;queue<int>q;//队列存所有更新过的点dist[1]=0;q.push(1);//入队while(q.size()){int t=q.front();//拿出一个元素q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];//首先更新if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];//先更新if(!st[j])//只有队列里面没有的时候才能入队{q.push(j);st[j]=true;}}}}if(dist[n]==0x3f3f3f3f)return -1;return dist[n];
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);}int t=spfa();if(t==-1)puts("impossible");else cout<<t<<endl;return 0;
}

五、spfa算法判断是否有负环

通过最短路的边数来判断是否有负环 。

#include<bits/stdc++.h>
//852 spfa判断是否
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx,w[N];
int dist[N];
bool st[N];
int cnt[N];//记录边数
int n,m;
void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;}
int spfa()
{memset(dist,0x3f,sizeof dist);memset(st,false,sizeof st);dist[1]=0;queue<int>q;//队列存所有更新过的点//因为有可能负环从第一个结点到不了所以把所有结点放到队列for(int i=1;i<=n;i++)q.push(i),st[i]=true;dist[1]=0;while(q.size()){int t=q.front();//拿出一个元素q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];//首先更新if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];//先更新cnt[j]=cnt[t]+1;if(cnt[j]>n)return 1;if(!st[j])//只有队列里面没有的时候才能入队{q.push(j);st[j]=true;}}}}return 0;
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);}int t=spfa();if(spfa())puts("Yes");else puts("No");
}

六、弗洛伊德Floyd算法求多源最短路

三重循环

#include<bits/stdc++.h>
//852 spfa判断是否
using namespace std;
const int N=210,INF=1e9;
int d[N][N];
int n,m,Q;
void floyd()
{for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{cin>>n>>m>>Q;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)d[i][j]=0;else d[i][j]=INF;}}while(m--){int a,b,c;cin>>a>>b>>c;d[a][b]=min(d[a][b],c);}floyd();while(Q--){int a,b;cin>>a>>b;if(d[a][b]<INF/2) cout<<d[a][b]<<endl;else cout<<"imposible"<<endl;}}