图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
程序员文章站
2022-03-31 08:17:59
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)V代表顶点个数 E代表边数Dijkstra算法 适合正权(不含负权)稠密图 时间复杂度为O(V^2) 只与顶点个数有关 慎用邻接矩阵 需要考虑初始化为INF 有向图和无向图 重边 和 自环//Acwing 849#includeusing namespace std;const int V=1e3;//最大顶点个数c...
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
V代表顶点个数 E代表边数
-
Dijkstra算法 适合正权(不含负权)稠密图 时间复杂度为O(V^2) 只与顶点个数有关 慎用邻接矩阵 需要考虑初始化为INF 有向图和无向图 重边 和 自环
//Acwing 849 #include<iostream> using namespace std; const int V=1e3;//最大顶点个数 const int INF = 1e9; int adj[V][V]; //邻接矩阵 在存入数据的时候记得考虑初始化,以及无向图和有向图处理方式不同 还要考虑 重边和自环的问题 bool used[V]; //判断是否使用过 int d[V]; //最短距离 int n,m,ts,te; //无向图 给你n个顶点 m条边 求从ts到特最短路径 int Dijkstra(); int main() { scanf("%d%d%d%d",&n,&m,&ts,&te); fill(adj[0],adj[0]+V*V,INF); //邻接矩阵一定要初始化为INF for(int i=0;i<m;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); adj[a][b] = adj[b][a] = w; } int t=Dijkstra(); if(t==INF) printf("impossible"); //此路不通 else printf("%d",t); //输出最短路径 } int Dijkstra() { fill(used,used+V,false); //初始化 fill(d,d+V,INF); d[ts]=0; //起点最短路径必须设为0 while(1) { int v=-1; for(int i=1;i<=n;i++) { //寻找一个没有使用过的距离起点最近的点 if(!used[i]&&(v==-1||d[v]>d[i])) v=i; } if(v==-1) break; //全部都使用过了 used[v]=true; for(int j=1;j<=n;j++) { //更新最短路径 d[j] = min(d[j],d[v]+adj[v][j]); } } return d[te]; }
-
堆优化Dijkstra算法 适合正权稀疏图 时间复杂度O(E logV )
//Acwing850 //使用 优先队列 d[V] pair<int,int> #include<iostream> #include<queue> using namespace std; const int INF=1e9,V=1e6; int d[V]; struct edge {int to,cost;}; vector<edge> G[V]; typedef pair<int,int> P; int n,m; int quickDij(); int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edge e={b,w} G[a].push_back(e); } int t=quickDij(); if(t==INF) printf("-1"); else printf("%d",t); } int quickDij() { priority_queue<P,vector<P>,greater<P>> que; //p.first存的是最短距离 p.second存的是顶点 fill(d,d+V,INF); d[1]=0; que.push(P(0,1)); while(que.size()) { P p=que.top(); que.pop(); int v=p.second; if(d[v]<p.first) continue; //冗余了 for(int i=0;i<G[v].size();i++) { edge e=G[v][i]; if(d[e.to] > d[v] + e.cost) { d[e.to] = d[v]+e.cost; que.push(P(d[e.to],e.to)); } } } return d[n]; }
-
Bellmon-Ford算法 适合有负权的图 边数限制的最短路径问题只能用它来求解 时间复杂度 O(V*E)
//Acwing 853 //n个顶点让你求从1到n边数不超过k的最短路径 #include<iostream> #include<cstring> using namespace std; const int INF=1e9,V=600,E=1e6; int d[V],backup[V]; //backup用于保留上一次d迭代结果 防止发生串联反应 无法控制边的数量 int Bellmon(); int n,m,k; struct edge { int a,b,w; }; edge es[E]; //存放给的所有边 尽量大 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); es[i]={a,b,w}; } int t=Bellmon(); if(t==INF) printf("impossible"); //或者这句话改为t>INF/2 就可以去掉 下面的if(backup[e.a]!=INF) 就代表没有通路 因为存在负权 有的影响INF else printf("%d",t); } int Bellmon() { fill(d,d+V,INF); d[1]=0; for(int i=0;i<k;i++){ memcpy(backup,d,sizeof d); for(int j=0;j<m;j++) { edge e=es[j]; if(backup[e.a]!=INF) //防止存在负权 对那些明明无法联通的点却改变INF d[e.b] =min(d[e.b],backup[e.a]+e.w); //用上一次迭代结果更新 防止发生串联 } } return d[n]; }
-
SPFA 适合绝大多数情况 但可能被卡样例 存在负圈无法求解 时间复杂度最好是 O(E)
最坏 O(V*E)
//Acwing 851 #include<iostream> #include<queue> using namespace std; const int V=1.5e5,INF=1e9; int d[V]; int nums[V]; //加上这个可以判断负圈 struct edge { int to,cost; }; vector<edge> G[V]; int SPFA(); int n,m; bool qj[V]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edge e={b,w}; G[a].push_back(e); } int t=SPFA(); if(t>INF/2) printf("impossible"); else printf("%d",t); } int SPFA() { fill(qj,qj+V,false); fill(d,d+V,INF); fill(nums,nums+V,0); d[1]=0; queue<int> q; q.push(1); qj[1]=true; nums[1]++; while(q.size()) { int p=q.front(); q.pop(); qj[p]=false; for(int i=0;i<G[p].size();i++) { edge e = G[p][i]; if(d[e.to]>d[p]+e.cost) { d[e.to] = d[p]+e.cost; if(!qj[e.to]){ q.push(e.to); qj[e.to]=true; } nums[e.to]++; if(nums[e.to]>n) return -1; //一个顶点入队超过n次就是图中存在负圈 } } } return d[n]; }
-
Floyd-Warshall 多源路径求解 O(V^3)
int d[MAX_V][MAX_V]; //d是邻接矩阵 循环结束就是i-->j最短路径 V 是顶点个数 for(int k=0;k<V;k++) for(int i=0;i<V;i++) for(int j=0;j<v;j++) d[i][j] = d[i][k] + d[k][j];
本文地址:https://blog.csdn.net/Y810614/article/details/110143980