[C] Bellman-Ford边松弛:解决负权边

news/2024/2/28 5:59:28

Bellman-Ford

  • Dijkstra算法是不能解决负权边的,而Bellman-Ford可以完美解决负权边的问题,还可以判断负权回路哦~
  • Dijkstra算法传送门:Dijkstra算法——通过边实现松弛
  • Bellman-Ford的核心代码只有4行:
    //Bellman-Ford 算法核心语句for (k = 1; k <= n - 1; k++)for (i = 1; i <= m; i++)if (dis[v[i]] > dis[u[i]] + w[i])dis[v[i]] = dis[u[i]] + w[i];
  • 上面代码的意思是:看看能否通过u[i]->v[i](权值为w[i])的这条边,使得1号顶点到v[i]的距离变短。
  • 即:1号顶点到u[i]的距离(dis[u[i]])加上u[i]->v[i]这条边(w[i])是否会比原来的dis[v[i]]更小。
  • 对于每条边,都这样松弛一遍。

在这里,往往dis数组松弛到一个程度后就不再变化,可以用另外一个数组对dis数组进行备份,当dis数组不再变化时,跳出循环。

当全部松弛完后,如果还能松弛,则此图有负权回路。(负权回路很好理解,走完这条回路,我的计步器居然不增反减?这是一个很不科学的路,但是在题目中难免会遇到~~)


代码实现

这次的代码真是短啊~

#include<stdio.h>
//int a[2000][2000];
int u[2000], v[2000], w[2000];
int inf = 99999999;
int dis[2000];
//int book[2000];
int main()
{int i, j, k, m, n, x, y, s;int min;scanf("%d %d", &n, &m);//读入边for (i = 1; i <= m; i++)scanf("%d %d %d", &u[i], &v[i], &w[i]);for (i = 1; i <= n; i++)dis[i] = inf;dis[1] = 0;//Bellman-Ford 算法核心语句for (k = 1; k <= n - 1; k++)for (i = 1; i <= m; i++)if (dis[v[i]] > dis[u[i]] + w[i])dis[v[i]] = dis[u[i]] + w[i];//输出结果for (i = 1; i <= n; i++)printf("%d ", dis[i]);return 0;
}

检测负权回路的代码

  • 加在输出之前就可以了
    //检测负权回路int flag = 0;for (i = 1; i <= m; i++){if (dis[v[i]] > dis[u[i]] + w[i]){printf("此图有负权回路\n");}}

运行结果:
在这里插入图片描述


http://www.ppmy.cn/news/607544.html

相关文章

大数据必学Java基础(二十三):方法的定义/调用/重载

文章目录 方法的定义/调用/重载 一、方法的定义和调用 1、什么是方法? 2、方法

Python 正则表达式各种特殊符号 重点

Python 正则表达式 正则表达式是一个特殊的字符序列&#xff0c;它能帮助你方便的检查一个字符串是否与某种模式匹配。 Python 自1.5版本起增加了re 模块&#xff0c;它提供 Perl 风格的正则表达式模式。 re 模块使 Python 语言拥有全部的正则表达式功能。 compile 函数根据…

st计算机编程语言,初学ST语言,有了这篇ST编程语言的相关知识就容易多了~

最近想学习ST语言&#xff0c;想要ST语言以及功能块的相关内容&#xff1f;小编给大家分享一下现成的一些资料。至于更多的ST资料&#xff0c;需要自己慢慢历练与积累。这话是论坛里版主说的。结构化文本(ST-Strutured Text)是一种高级的文本语言&#xff0c;可以用来描述功能&…

[JS] 如何判断一个对象是否为空

js判断空对象的几种方法 一、将对象转为字符串比较 let a {} console.log(JSON.stringify(a) {}) //true二、for…in循环 function isEmpty(obj) {for (let key in obj) {return false}return true } console.log(isEmpty(a)) //true三、Object.getOwnPropertyNames() Ob…

大数据必学Java基础(二十四):数组的引入和学习

文章目录 数组的引入和学习 一、数组的引入 1、习题引入 二、数组的学习

低数值精度推理和训练

低数值精度推理和训练 介绍 如今&#xff0c;大多数商业深度学习应用程序使用 32 位浮点精度 ( ) 来处理训练和推理工作负载。各种研究人员已经证明&#xff0c;深度学习训练和推理都可以以较低的数值精度进行&#xff0c;使用 16 位乘法器进行训练&#xff0c;使用 8 位乘法器…

数据湖(十五):Spark与Iceberg整合写操作

文章目录 Spark与Iceberg整合写操作 一、INSERT INTO 二、MERGE INTO

TVM量化路线图roadmap

TVM量化路线图roadmap INT8量化方案 本文介绍了量化过程的原理概述&#xff0c;提出了在TVM中实现量化过程的建议。  介绍量子化的背景知识  INT8量化-后端代码生成  这个线程只关注TVM中量化层的实现 量子开发 基于搜索的自动量化 提出了一种新的量化框架&#xff0c;…

python 列表生成式、lower()和upper()的使用

参考&#xff1a; http://www.liaoxuefeng.com/wiki/001374738125095c955c1e6d8bb493182103fac9270762a000/00138681963899940a998c0ace64bb5ad45d1b56b103c48000 ########################################## lower()&#xff1a;字符串缩小&#xff1a; sASDFss.lower() uppe…

寒武纪智能系统参数

寒武纪智能系统参数 • 思元290 • MLU290-M5智能加速卡 • MLU290-M5 • MLU290-M5智能加速卡搭载寒武纪首颗训练芯片思元290&#xff0c;采用台积电7nm先进制程工艺&#xff0c;采用MLUv02扩展架构&#xff0c;集成了高达460亿的晶体管。MLU290-M5智能加速卡采用开放加速模块…

电脑总有安装计算机更新,为什么我们的电脑总会莫名的安装垃圾软件,看完吓一跳,欢迎关注...

现在电脑已经走进了我们的生活&#xff0c;很多人都已经接触电脑了&#xff0c;然而对于电脑的使用&#xff0c;我们除了知道那些最常见的使用方式之外&#xff0c;大多数人对电脑的其他功能任然是一无所知&#xff0c;当然学习电脑专业和IT的除外了&#xff0c;很多人应该都会…

大数据必学Java基础(二十五):数组的三种初始化方式

文章目录 数组的三种初始化方式 一、静态初始化 二、动态初始化 三、默认初始化 <

数据库中的Schema是什么?

在数据库中&#xff0c;schema&#xff08;发音 “skee-muh” 或者“skee-mah”&#xff0c;中文叫模式&#xff09;是数据库的组织和结构&#xff0c;schemas andschemata都可以作为复数形式。模式中包含了schema对象&#xff0c;可以是表(table)、列(column)、数据类型(data …

GPU指令集技术分析

GPU指令集技术分析 本文将两篇文章整理了一下。 参考文章链接如下&#xff1a; https://zhuanlan.zhihu.com/p/391238629 https://zhuanlan.zhihu.com/p/166180054 一&#xff0e;GPGPU- 指令执行设计 本节主要内容&#xff1a; • GPGPU指令执行简介 o GPGPU指令执行流水线 o …

云原生(三十三) | Kubernetes篇之平台存储系统部署

文章目录 Kubernetes平台存储系统部署 一、查看前提条件 二、部署&修改operator 三、部署集群

mac端锐捷无法验证服务器,MAC地址免认证不成功处理思路

步骤1、 检查在SMP上开启MAC地址免认证的MAC不准确点击查看电脑PC的MAC地址&#xff0c;获取到物理地址&#xff1b;以太网适配器 本地连接:连接特定的 DNS 后缀 . . . . . . . :描述. . . . . . . . . . . . . . . : Intel(R) 82579LM Gigabit Network Connection物理地址. . …

python 3计算KL散度(KL Divergence)

程序 利用python 3计算 import numpy as np import scipy.stats# 随机生成两个离散型分布 x [np.random.randint(1, 11) for i in range(10)] print(x) print(np.sum(x)) px x / np.sum(x) print(px) y [np.random.randint(1, 11) for i in range(10)] print(y) print(np.su…

大数据必学Java基础(二十六):数组的应用题

文章目录 数组的应用题 一、最值问题

EUV极紫外光刻技术

EUV极紫外光刻技术 &#xff08;1&#xff09;极紫外光 波长为 13.5nm 的极紫外 (EUV) 光刻系统的最新发展&#xff0c;以取代 193i 光刻。为了应对多图案成本上升的趋势&#xff0c;EUV 系统在曝光吞吐量&#xff08;每小时晶圆数&#xff09;&#xff0c;曝光强度和系统正常运…

极致呈现系列之:Echarts主题河流图的绚丽世界

目录 什么是主题河流图Echarts主题河流图的特点和应用场景Echarts主题河流图的特点Echarts主题河流图的应用场景 Echarts中主题河流图的常用配置项vue3中创建主题河流图 什么是主题河流图 主题河流图&#xff08;Theme River Chart&#xff09;是Echarts中的一种数据可视化图表…
最新文章