给定一张有向图，若对于图中的某一条边(x,y,z)，有dist[y]≤dist[x]+z成立，则称该边满足三角形不等式。如果所有边都满足三角形不等式，则dist数组就是所求的最短路。
bellman-ford算法
(x,y,z)表示的是一条从 x 出发， 到达 y ，长度为 z 的有向边。
首先介绍基于迭代的bellman-ford算法，它的流程如下：
1.扫描所有边(x,y,z)，若dist[y]＞dist[x]+z, 则用dist[x]+z更新dist[y]
2.重复上述操作，直到没有更新操作发生。
bellman-ford算法的时间复杂度是o(nm)
通过bellman-ford算法我们可以求解有边数限制的最短路问题。
例题：acwing 853. 有边数限制的最短路
算法步骤
初始化 dist 数组为正无穷， dist[1] = 0
（外重循环）循环 i 从 1 到 n ，遍历 n 次表示：是不经过超过 i 条边到达终点的最短距离
（内重循环）循环 i 从 1 到 m， 遍历 m 条边，把所有的边都进行松弛操作：
每次取出两点以及以及连接他们的权重 (a,b,w)
用以下公式更新最短距离： dist[b]=min(dist[b],dist[a]+w)
注意点：
需要把dist数组进行一个备份，这样防止每次更新的时候出现串联
由于存在负权边，所以 return -1 的条件是dist[n]＞0x3f3f3f/2
代码实现
#include <iostream> #include <cstring> using namespace std; const int n = 510, m = 10010; struct edge { int a, b, w; }e[m]; // 存下每一条即可 int dist[n]; int back[n]; // 备份数组放置串联 int n, m, k; void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for(int i = 0; i < k; i ++ ) // 不超过k条边 { memcpy(back, dist, sizeof back); for(int j = 0; j < m; j ++ ) // 遍历所有边 { int a = e[j].a, b = e[j].b, w = e[j].w; dist[b] = min(dist[b], back[a] + w); } } } int main() { cin >> n >> m >> k; for(int i = 0; i < m; i ++ ) { int a, b, w; scanf("%d%d%d", &a, &b, &w); e[i] = {a, b, w}; } bellman_ford(); if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else cout << dist[n] << endl; return 0; }
spfa算法
spfa算法在国际上通称为“队列优化的“bellman-ford算法”。
spfa算法的流程如下：
1.建立一个队列，起初队列中只含有起点1
2.取出头结点 x ，扫描它的所有出边(x,y,z)，若dist[y]＞dist[x]+z，则使dist[y]用dist[x]+z来更新。同时若y不再队列中，则将y入队
在任意时刻，该算法的队列都保持了该拓展的节点。每次入队都相当于完成了一次 dist 数组的更新操作，使其满足三角不等式。一个节点可能会入队、出队多次。最终，图中所有的结点全部收敛到全部满足三角不等式的状态。
这个队列避免了对bellman-ford算法中不需要拓展的多余结点的冗余扫描，在随机图上的运行效率o(km)级别，其中 k 是一个很小的常数。
代码实现
spfa求最短路
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int n = 1e6 + 10; int n, m; int h[n], e[n], w[n], ne[n], idx; int dist[n]; bool st[n]; void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ; } void spfa() { memset(dist, 0x3f, sizeof dist); queue<int> q; dist[1] = 0; st[1] = true; q.push(1); while(q.size()) { int t = q.front(); q.pop(); st[t] = false; for(int i = h[t]; ~i; 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; } } } } } 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(); if(dist[n] == 0x3f3f3f3f) puts("impossible"); else printf("%d",dist[n]); return 0; }
以上就是c++图论之bellman-ford算法和spfa算法的实现的详细内容，更多关于c++ bellman-ford spfa算法的资料请关注<计算机技术网(www.ctvol.com)!!>其它相关文章！
需要了解更多c/c++开发分享C++图论之Bellman-Ford算法和SPFA算法的实现，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/1237867.html