一、最短路问题
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;
}
}