有边数限制的最短路——Bellman Ford算法
2022/7/27 1:24:52
本文主要是介绍有边数限制的最短路——Bellman Ford算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目传送门
首先我们来认识一下Bellman Ford算法,Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
实现过程
- 迭代 \(n\) 次
- 遍历 \(m\) 条边的信息 \(a,b,w\) 表示结点 \(a,b\) 之间有一条边权为 \(w\) 的边
- 每次遍历进行一次松弛操作:\(dis_b=min(dis_b,back_a+w)\)
其中 \(back\) 数组表示的是 \(dis\) 数组的备份,防止出现串联问题,就是用这一次更新的节点更新后面的结点。
那接下来就是解决这道例题了
我们这里只要迭代 \(k\) 次即可
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 510, M = 1e4 + 100; int n,m,k; int dist[N], backup[N];//backup防止串联 struct node{ int a,b,w; }edge[M]; int bellman() { 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 = edge[j].a, b = edge[j].b, w = edge[j].w; dist[b] = min(dist[b], backup[a] + w); } } return 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); edge[i] = {a,b,w}; } int t = bellman(); if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n", t); return 0; }
时间复杂度\(O(nm)\)
这篇关于有边数限制的最短路——Bellman Ford算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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?