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$。

  • 若 $w \geq 0$,则表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边,还存在一条从 $v$ 至 $u$ 边权为 $w$ 的边。
  • 若 $w < 0$,则只表示存在一条从 $u$ 至 $v$ 边权为 $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

样例输出 #1

NO
YES

提示

数据规模与约定

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

  • $1 \leq n \leq 2 \times 10^3$,$1 \leq m \leq 3 \times 10^3$。
  • $1 \leq u, v \leq n$,$-10^4 \leq w \leq 10^4$。
  • $1 \leq T \leq 10$。

提示

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

思路

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

代码

相关文章
|
10月前
|
算法
最短路之Floyd算法
最短路之Floyd算法
99 1
|
10月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
56 0
|
10月前
|
算法
最短路之Dijkstra算法
最短路之Dijkstra算法
75 0
|
10月前
|
算法
class065 A星、Floyd、Bellman-Ford与SPFA【算法】
class065 A星、Floyd、Bellman-Ford与SPFA【算法】
83 0
|
10月前
|
算法
讲课:拓扑排序、最短路算法
讲课:拓扑排序、最短路算法
|
10月前
|
存储 算法
最短路之SPFA算法
最短路之SPFA算法
72 0
|
10月前
|
算法 定位技术 索引
class064 Dijkstra算法、分层图最短路【算法】
class064 Dijkstra算法、分层图最短路【算法】
89 0
|
算法
图论算法(最短路、网络流、二分图)
图论算法(最短路、网络流、二分图)
119 0
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于生物地理算法的MLP多层感知机优化matlab仿真
本程序基于生物地理算法(BBO)优化MLP多层感知机,通过MATLAB2022A实现随机数据点的趋势预测,并输出优化收敛曲线。BBO模拟物种在地理空间上的迁移、竞争与适应过程,以优化MLP的权重和偏置参数,提升预测性能。完整程序无水印,适用于机器学习和数据预测任务。
|
5天前
|
资源调度 算法 数据可视化
基于IEKF迭代扩展卡尔曼滤波算法的数据跟踪matlab仿真,对比EKF和UKF
本项目基于MATLAB2022A实现IEKF迭代扩展卡尔曼滤波算法的数据跟踪仿真,对比EKF和UKF的性能。通过仿真输出误差收敛曲线和误差协方差收敛曲线,展示三种滤波器的精度差异。核心程序包括数据处理、误差计算及可视化展示。IEKF通过多次迭代线性化过程,增强非线性处理能力;UKF避免线性化,使用sigma点直接处理非线性问题;EKF则通过一次线性化简化处理。

热门文章

最新文章