Bellman-Ford算法求最短路和负环

简介: Bellman-Ford算法求最短路和负环

Bellman-Ford算法(O(nm)

Bellman-Ford(贝尔曼-福特)算法基于松弛操作的单源最短路算法。

e[u]存u点的出边的邻点和边权,d[u]存u点到源点的距离。

  1. 初始化,ds]=0,d[其它点]=+o;
  2. 执行多轮循环。每轮循环,对所有边都尝试进行一次松弛操作;
  3. 当一轮循环中没有成功的松弛操作时,算法停止

为什么最坏需要n-1轮循环:n-1轮循环可以保证在有n个顶点的图中,从源节点到任意其他节点的最短路径都可以被找到。因为最长的简单路径最多包含n-1条边,所以进行n-1轮的松弛操作足以找到所有最短路径。

【模板】负环

题目描述

给定一个 n 个点的有向图,请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是:一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据

输入的第一行是一个整数 T,表示测试数据的组数。对于每组数据的格式如下:

第一行有两个整数,分别表示图的点数 n 和接下来给出边信息的条数 m

接下来 m 行,每行三个整数 u,v,w

  • w0,则表示存在一条从 uv 边权为 w 的边,还存在一条从 vu 边权为 w 的边。
  • w<0,则只表示存在一条从 uv 边权为 w 的边。

输出格式

对于每组数据,输出一行一个字符串,若所求负环存在,则输出 YES,否则输出 NO

样例 #1

样例输入 #1

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
AI 代码解读

样例输出 #1

NO
YES
AI 代码解读

提示

数据规模与约定

对于全部的测试点,保证:

  • 1n2×1031m3×103
  • 1u,vn104w104
  • 1T10

提示

请注意,m 不是图的边数。

思路

利用Bellman-ford算法求负环即可,模版题

代码

目录
打赏
0
0
0
0
0
分享
相关文章
|
10月前
|
最短路之Floyd算法
最短路之Floyd算法
101 1
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
57 0
|
10月前
|
最短路之Dijkstra算法
最短路之Dijkstra算法
75 0
|
10月前
|
class065 A星、Floyd、Bellman-Ford与SPFA【算法】
class065 A星、Floyd、Bellman-Ford与SPFA【算法】
88 0
|
10月前
|
讲课:拓扑排序、最短路算法
讲课:拓扑排序、最短路算法
|
10月前
|
最短路之SPFA算法
最短路之SPFA算法
73 0
class064 Dijkstra算法、分层图最短路【算法】
class064 Dijkstra算法、分层图最短路【算法】
94 0
图论算法(最短路、网络流、二分图)
图论算法(最短路、网络流、二分图)
123 0
基于生物地理算法的MLP多层感知机优化matlab仿真
本程序基于生物地理算法(BBO)优化MLP多层感知机,通过MATLAB2022A实现随机数据点的趋势预测,并输出优化收敛曲线。BBO模拟物种在地理空间上的迁移、竞争与适应过程,以优化MLP的权重和偏置参数,提升预测性能。完整程序无水印,适用于机器学习和数据预测任务。
基于LSB最低有效位的音频水印嵌入提取算法FPGA实现,包含testbench和MATLAB对比
本项目展示了一种基于FPGA的音频水印算法,采用LSB(最低有效位)技术实现版权保护与数据追踪功能。使用Vivado2019.2和Matlab2022a开发,完整代码含中文注释及操作视频。算法通过修改音频采样点的最低有效位嵌入水印,人耳难以察觉变化。然而,面对滤波或压缩等攻击时,水印提取可能受影响。该项目运行效果无水印干扰,适合实时应用场景,核心逻辑简单高效,时间复杂度低。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等