当前位置：首页 > news >正文

搜索与图论复习2最短路

news 来源：原创 2025/5/17 8:19:25

单源最短路---所有边权是正数(Dijkstra算法O(n^2)--稠密图(邻接矩阵)和堆优化的Dijkstra算法O(mlogn)--稀疏图(邻接表)) 或存在负边权(Bellman-ford贝尔曼福特算法O(nm)和SPFA一般O(m) 最坏O(nm) )

多源最短路---Floyd算法O(n^3)

一、迪杰斯特拉算法(Dijkstra)：1dist[1]=0,dist[v]=正无穷。2for(v的0~n)，s是当前已经确定最短路径的点，t是不在s中的距离最近的点，t放进s中，用t更新其他点的距离（dist[x]>dist[t]+w）更新。通过邻接矩阵存图。

#include<iostream>
#include<cstring> 
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++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;//找到dist最小的点 }if(t==n)break;//优化 st[t]=true;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(){cin>>n>>m;memset(g,0x3f,sizeof(g));while(m--){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);}int t=dijkstra();cout<<t<<endl;return 0;
}

二、堆优化的迪杰斯特拉算法：优化在n个数中找距离最近的点O(n^2)用堆优化

#include<iostream>
#include<cstring> 
#include<queue> 
using namespace std;
typedef pair<int,int>PII;
const int N=150010;
int n,m;
int h[N],e[N],ne[N],idx,w[N];//权重 
int dist[N];
bool st[N];//是否已经确定最短路 
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;//起点 priority_queue<PII,vector<PII>,greater<PII>>heap;heap.push({0,1});//从1点开始,0为距离 while(heap.size()){auto t=heap.top();heap.pop();int ver=t.second,distance=t.first;if(st[ver])continue;st[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;else 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=dijkstra();cout<<t<<endl;return 0;
}

三、Bellman-Ford算法for循环n次，(备份)for所有边a,b,w表示所有a到b的边权值为w，(松弛)，处理有福权边，能判断是否有负环(但是一般用SPFA做)

- 第 k 次松弛：找到经过最多 k 条边的最短路径。
通过多次松弛，算法可以逐步覆盖从起点到所有节点的所有可能路径

#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++){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)return -0x3f3f3f3f;else return dist[n];
}
int main(){cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;edges[i]={a,b,c};}int t=bellman_ford();if(t==-0x3f3f3f3f)cout<<"impossible"<<endl;else cout<<t<<endl;return 0;
}

四、SPFA算法：用队列，只要有变小就取出队头，更新t的所有出边，成功就加入队列（更新过谁就拿谁来操作）通过队列优化 Bellman-Ford 算法，只对距离发生变化的节点进行松弛操作。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N=100010;
int dist[N];
bool st[N];
int h[N],e[N],ne[N],idx,w[N];
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int 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)return -0x3f3f3f3f;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==-0x3f3f3f3f)cout<<"impossible"<<endl;else cout<<t<<endl;return 0;
}

补充负环判断：维护cnt[x]=cnt[t]+1，的数组，如果cnt[x]>=n存在负环。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010,M=10010;
int h[N],e[M],ne[M],idx,w[M];
int dist[N],cnt[N];
bool st[N];
int n,m;
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){queue<int>q;for(int i=1;i<=n;i++){q.push(i);st[i]=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)return true;if(!st[j]){q.push(j);st[j]=true;}}}}return false;
}
int main(){cin.tie(0),cout.tie(0);ios::sync_with_stdio(false);cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);}if(spfa())cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

五、Floyd算法：基于动态规划三层for枚举d(i,j)=min(d(i,j)，d(i,k)+d(k,j))。

#include<iostream>
#include<cstring> 
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(){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,w;cin>>a>>b>>w;d[a][b]=min(d[a][b],w);}floyd();while(Q--){int a,b;cin>>a>>b;if(d[a][b]>INF/2)cout<<"impossible"<<endl;else cout<<d[a][b]<<endl;}return 0;
}

相关文章：