目录
一、单源最短路问题
问题定义:
1.朴素dijkstra算法O(n²)
适用于稠密图
- 算法原理
- 维护一个距离数组
dist
,用来记录从源点到各个顶点的最短距离,初始时,源点到自身的距离为 0,到其他顶点的距离为无穷大。 - 还需要一个标记数组
st
,用于记录哪些顶点的最短距离已经确定。 - 每次从尚未确定最短距离的顶点中,选择距离源点最近的顶点
u
,标记u
的最短距离已确定。然后遍历u
的所有邻接顶点v
,如果通过u
到达v
的距离比当前记录的dist[v]
更小,则更新dist[v]
。
- 维护一个距离数组
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++){ //迭代n次
int t=-1;//t记录该轮确定的距离最短点
for(int j=1;j<=n;j++){//从未确定最短距离点中找距离最小的点
if(!st[j]&&(t==-1||dist[t]>dist[j])){
t=j;
}
}
st[t]=true;
if(t==n) break;//优化
//用这轮标记的点来更新未标记的点
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
printf("%d\n",t);
return 0;
}
2.堆优化 Dijkstra 算法O(mlogn)
适用于稀疏图
- 算法原理
- 与朴素 Dijkstra 算法的不同在于,它使用堆(通常是优先队列)来优化寻找当前距离源点最近的未确定顶点的过程。
- 优先队列中存储的是顶点以及从源点到该顶点的当前最短距离,每次从优先队列中取出距离最小的顶点,然后对其邻接顶点进行距离更新操作。如果更新后的距离更小,则将新的距离和顶点信息放入优先队列中。
由于该图顶点和边数目都多,用二维数组(邻接矩阵)存储空间占用大,故考虑用邻接表
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
//邻接表存储
int h[N],w[N],e[N],ne[N],idx;
int dist[N];//dist[i]表示结点1到结点n的距离
bool vis[N];//vis[i]表示结点i是否拓展过(该点最短距离固定)
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof(dist));//初始距离为大数
dist[1]=0;//初始化第一个结点到自己距离为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(vis[ver]) continue;
vis[ver]=true;//若没扩展,拿他进行扩展
for(int i=h[ver];i!=-1;i=ne[i]){ //遍历其每一条边
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push({dist[j],j}); //更新距离后放入堆中
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
cout<<dijkstra()<<endl;
return 0;
}
3.Bellman-Ford算法O(nm)
Bellman-Ford算法以边为单位,进行n次迭代,每次迭代更新一遍每个点到起点的距离。Bellman-Ford算法对边的存储没什么要求,直接用一个类存储(C ++使用结构体)即可。
当题目规定只能经过k条边的最短路径时,只能用Bellman-Ford算法。
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct Edge{
int a,b,w;
}edges[M];
int bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
//备份距离数组,每次更新时应该用上一次迭代后的dist数组进行更新
memcpy(backup,dist,sizeof dist);
for(int j=0;j<m;j++){
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
if(dist[n]>0x3f3f3f3f/2) puts("impossible"); //1压根到不了n,但有可能其它点(和1不连通+负权值)改变了到他的距离
else printf("%d\n",dist[n]);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i]={a,b,w};
}
bellman_ford();
return 0;
}
4.SPFA算法 O(m)/O(nm)
spfa算法是对Bellman-Ford算法的优化,Bellman-Ford每次都用当前点去更新其他点到起点的距离,如果当前点的距离没有变小的话,那么这个操作就是在浪费时间,所以spfa算法在此处进行了优化,利用一个队列,每当遍历到的点距离变小时,将其放入队列中,之后会用它去更新其他点的距离。
并且,spfa算法一般情况下很快,很多Dijkstra能做的spfa都能做,除了阴险的出题人编造数据时,将spfa算法时间复杂度卡成O(nm)的情况,spfa算法时间复杂度一般为O(m),最坏O(nm)。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
//邻接表存储
int h[N],w[N],e[N],ne[N],idx;
int dist[N];//dist[i]表示结点1到结点n的距离
bool st[N];//vis[i]表示结点i是否拓展过(该点最短距离固定)
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]=true;
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) puts("impossible");
else printf("%d\n",dist[n]);
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
spfa();
return 0;
}
应用-判断负环
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
//邻接表存储
int h[N],w[N],e[N],ne[N],idx;
int dist[N],cnt[N];//dist[i]表示结点1到结点n的距离
bool st[N];//vis[i]表示结点i是否拓展过(该点最短距离固定)
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//注意开始时需要将所有点加入队列,要不然求的只是1号点能到的负环
queue<int> q;
for(int i=1;i<=n;i++) q.push(i);
st[1]=true;
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){
cout<<"Yes";
return;
}
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
cout<<"No";
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
spfa();
return 0;
}
二、多元最短路问题O(
n³)
问题定义:
Floyd算法
Floyd算法基于动态规划,使用三重循环,可以求解多源汇问题。由于Floyd算法是最短路算法的最后一个算法,所以在此进行总结。朴素Dijkstra常用于求解正权图中的稠密图,时间复杂度O(n²)、堆优化版Dijkstra常用于求解正权图中的稀疏图,时间复杂度O(mlogn)、Bellman-Ford算法常用于求解有边数限制的最短路问题,时间复杂度O(nm)、spfa算法常用于求解存在负权边的最短路问题(也可以求正权边最短路,有被卡风险)、Floyd算法常用于求解多源汇最短路问题,时间复杂度O(n³)。
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=210,INF=1e9;
int n,m,Q;
int d[N][N];
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(){
scanf("%d%d%d",&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,w;scanf("%d%d%d",&a,&b,&w);
d[a][b]=min(d[a][b],w);//保留最短的重边
}
floyd();
while(Q--){
int a,b;scanf("%d%d",&a,&b);
if(d[a][b]>INF/2) puts("impossible"); //因为有负权边
else printf("%d\n",d[a][b]);
}
return 0;
}
标签:dist,idx,int,算法,Bellman,Ford,SPFA,距离,include From: https://blog.csdn.net/a2946501058/article/details/145145917