最短路算法合集
2024/3/9 11:32:27
本文主要是介绍最短路算法合集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
dijkstra算法
思路:
1、将所有顶点分为p、q两个集合,p已求出最短路径,q未求出最短路径。
2、令源点\(start\)到自己的距离为0,即\(dis[start]=0;\)
3、从p集合中找到距离源点最近的点,与之有边\(<u,v,w>\)相连的点v到源点的距离可更新为\(dis[v]=min(dis[v],dis[u]+w)\),不断重复直到q集合为空。
朴素版 O( \(n^2\) ):
#include<bits/stdc++.h> using namespace std; const int N = 510, M=1e5+10,INF = 0x3f3f3f3f; int dis[N], vis[N],h[N],to[M],w[M],ne[M],idx; int n, m, start; void add(int u,int v,int c) { to[++idx]=v; w[idx]=c; ne[idx]=h[u]; h[u]=idx; } void dijkstra() { memset(dis,0x3f,sizeof dis); dis[start] = 0; //起点距离为0 for (int i = 1; i <= n; i++) { int t = -1; for (int j = 1; j <= n; j++)//在还未确定最短路的点中,找到距离最小的点 if (!vis[j] && (t == -1 || dis[j] < dis[t])) t = j; vis[t] = 1; for (int j = h[t]; j != -1; j=ne[j]) { //用t更新其他点的距离 int k=to[j]; dis[k] = min(dis[k], dis[t] + w[j]); } } } int main() { cin >> n >> m ; memset(h,-1,sizeof h); //初始化h数组 int x, y, z; for (int i = 1; i <= m; i++) { //输入边 cin >> x >> y >> z; add(x,y,z); } start = 1; dijkstra(); if (dis[n] == INF) cout << -1; else cout << dis[n]; return 0; }
堆优化版O(\(m\ log_n\)):
优化思路:时间开销主要在查找距离p集合最近的点,可以使用优先队列进行优化。
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> PII; const int N = 2e5, M = N * 2; int n, m, s; int h[N], to[M], w[M], ne[M], idx; int dis[N]; bool vis[N]; void add(int u, int v, int c) { //链式前向星加边 to[++idx] = v; w[idx] = c; ne[idx] = h[u]; h[u] = idx; } void dijkstra() { memset(dis, 0x3f, sizeof dis); dis[s] = 0; priority_queue<PII, vector<PII>, greater<PII> > heap; //优先队列(小根堆) heap.push({0, s}); //把起点放入堆中 while (heap.size()) { //遍历堆 int t = heap.top().second; //取出堆顶元素,进行更新 heap.pop(); if (vis[t]) continue; vis[t] = true; for (int i = h[t]; i != -1; i = ne[i]) { int j = to[i]; if (dis[j] > dis[t] + w[i]) { //更新,松弛操作 dis[j] = dis[t] + w[i]; heap.push({dis[j], j}); } } } } int main() { memset(h, -1, sizeof h); cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } s=1; //起点是1 dijkstra(); if (dis[n] == 0x3f3f3f3f) cout << -1; else cout << dis[n]; return 0; }
补充:
建反向图:
1、反向图1
2、反向图2
Bellman_ford
思路:以每条边来松弛,如果发现终点能够通过该边使得路径变短,那么更新。
判断负环:在没有负环的图中,每个点最多被其他\(n-1\)个点各更新一次,如果被更新了第\(n\)次那么说明有负环。
复杂度\(O(nm)\)
适用条件:能够判断负环,可以有负权边。
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #define pii pair<int,int> #define INF 0x3f3f3f3f using namespace std; const int maxn=1e5+10; int n,m; int dis[maxn]; vector<pii>edge[150]; void in() { int a,b,c; for(int i=1; i<=m; i++) { cin>>a>>b>>c; edge[a].push_back(make_pair(b,c)); edge[b].push_back(make_pair(a,c)); } } void Bellman_ford(int st) { dis[st]=0; for(int k=1; k<n; k++) { //对应n-1伦操作 bool flag=1; for(int i=1; i<=n; i++) { for(int j=0; j<edge[i].size(); j++) { int u=i,v=edge[i][j].first,w=edge[i][j].second; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; flag=0; } } } if(flag)break; } for(int i=1; i<=n; i++) { for(int j=0; j<edge[i].size(); j++) { int u=i,v=edge[i][j].first,w=edge[i][j].second; if(dis[v]>dis[u]+w) { cout<<"fuhuan"; } } } } int main() { ios::sync_with_stdio(0); while(cin>>n>>m&&(n||m)) { for(int i=1; i<=n; i++)edge[i].clear(),dis[i]=INF; in(); Bellman_ford(1); cout<<dis[n]<<endl; } return 0; }
SPFA(优化版Bellman_ford)
优化思路:由于\(Bellman_ford\)的核心在于松弛操作,易得只有起点被更新了,才能够更新与它相连的点,只需使用队列记录能够更新其他点的点即可。
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<queue> #define pii pair<int,int> #define INF 0x3f3f3f3f using namespace std; const int maxn=1e5+10; int n,m; int dis[maxn]; bool vis[maxn]; int times[maxn]; vector<pii>edge[150]; int read() { int s=0,t=1; char c=getchar(); while(!isdigit(c)) { if(c=='-')t*=-1; c=getchar(); } while(isdigit(c)) { s=(s<<3)+(s<<1)+c-48; c=getchar(); } return s*t; } void in() { int a,b,c; for(int i=1; i<=m; i++) { a=read(); b=read(); c=read(); edge[a].push_back(make_pair(b,c)); edge[b].push_back(make_pair(a,c)); } } void SPFA(int st) { queue<int>q; vis[st]=1; q.push(st); dis[st]=0; while(q.size()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=0; i<edge[u].size(); i++) { int v=edge[u][i].first,w=edge[u][i].second; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) { q.push(v); vis[v]=1; times[v]++; if(times[v]==n)return ; } } } } } int main() { ios::sync_with_stdio(0); while(1) { n=read(); m=read(); if(n==m&&!n)break; for(int i=1; i<=n; i++)edge[i].clear(),dis[i]=INF; in(); SPFA(1); cout<<dis[n]<<endl; } return 0; }
这篇关于最短路算法合集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?