沃舍尔算法_Warshall算法和Floyd算法-程序员宅基地
技术标签： 沃舍尔算法
不用说这两位都是冷门算法……毕竟O(n^3)的时间复杂度算法在算法竞赛里基本算是被淘汰了……而且也没有在这个算法上继续衍生出其他的算法…
话说学离散的时候曾经有个把warshall算法简化到1/2时间的想法……不过懒得去翻了，现在想想本来这两个不用矩阵而用位运算的话速度不知道比我那个方法快多少倍……
嘛，切入正题吧，先讲warshall算法，其用来计算有向图的传递闭包，不知道概念的请去百度(躺
之前在学离散的时候还是花了点时间来研究这个算法的，但是仔细看了下书上的就发现和书上写的有些不一样，下面讲讲我知道的那种和书上的那种:
我知道的那种：
将有向图的邻接矩阵进行相乘操作，每乘一次保存结果，原本的矩阵称为R(1)，再乘以R(1)称为R(2),再乘以R(1)称为R(3)…直到取到R(n-1)为止。将R1….Rn-1取并，得出相连矩阵结果。
原理，易证，将邻接矩阵相乘所得为比当前路线高一阶的相连矩阵，假设R1为所有路径为1的通路，那么R2就是所有路径为2的通路。。。Rn-1就是所有路径为n-1的通路。因为只有n个节点，假设求得路线不存在环，那最多为n-1长度，可从之前结果获得，假设存在环，那么环的结果再之前便已经取得。无论怎样，其并结果绝对包含所有节点的链接关系。
书上新看到的：
for k in vertex
for i in row
for j in col
如果点i,k.col存在相连关系，k.row,j存在相连关系，那么这个点就是可以被连上的。
同样的，floyd也是这个尿性，不过里面得改一下：
若能相连，看看是不是比现在的值小，小的就换上。
嘛，怎么说肯定不是很理解，所以我就用例子说明一下把：
这样的一张图，邻接矩阵的样式为：
a b c d
a 0 n 3 n
b 2 0 n n
c n 7 0 1
d 6 n n 0
布尔值的样式是：
a b c d
a 0 n 1 n
b 1 0 n n
c n 1 0 1
d 1 n n 0
那么，warshall的做法是，先统计第1行和第1列，发现(d,c)列对应的(a,c)(第一行)，和(d,a)(第一列)都为1，则(d,c)变为1，同理，(b,c)变为1，那么第一轮的结果是：
a b c d
a 0 n 1 n
b 1 0 1 n
c n 1 0 1
d 1 n 1 0
第二轮：
a b c d
a 0 n 1 n
b 1 0 1 n
c 1 1 1 1
d 1 n 1 0
第三轮：
a b c d
a 1 1 1 1
b 1 1 1 1
c 1 1 1 1
d 1 1 1 1
至此，已经没有进行第四轮的必要，故这是一个全通图。floyd的思路与其类似，不过是判断是否两个关联值加起来是否小于当前值，小于的话那就更新，不然不更新。
智能推荐
Linux 驱动开发基础知识——编写LED驱动程序（三）_linux驱动怎么写-程序员宅基地
文章浏览阅读6.2k次，点赞43次，收藏29次。我们基于 Hello 驱动程序先写出最简单的 LED 驱动程序_linux驱动怎么写
RabbitMQ学习文档（环境安装篇）-程序员宅基地
文章浏览阅读270次。RabbitMQ学习文档_mq学习文档
希捷7200.11固件门完全DIY修正方法! 不用几块钱, DIYers请进!!!_希捷stcomtool转t失败-程序员宅基地
文章浏览阅读1.5w次，点赞2次，收藏9次。分享给有需要的朋友, 数据无价... 以后注意备份重要资料... 1. 老外的方法[By Gradius]: The Solution for Seagate 7200.11 HDDs (final and revised version): http://www.msfn.org/board/index.php?showtopic=128807&hl=7200.112. (第_希捷stcomtool转t失败
数据库安全：Hadoop 未授权访问-命令执行漏洞._hadoop未授权访问-程序员宅基地
文章浏览阅读2.9k次，点赞3次，收藏4次。Hadoop 未授权访问主要因HadoopYARN资源管理系统配置不当，导致可以未经授权进行访问，从而被攻击者恶意利用。攻击者无需认证即可通过RESTAPI部署任务来执行任意指令，最终完全控制服务器。_hadoop未授权访问
100个替代昂贵商业软件的开源应用_citadel开源中文版本-程序员宅基地
文章浏览阅读4.1k次，点赞3次，收藏18次。100个替代昂贵商业软件的开源应用面对大，中，小企业和家庭用户，立竿见影显著降低成本的开源软件。某些商业软件素以昂贵著称。随着云计算的日益普及，很多常用软件包供应商将一次性收费改为月租模式。虽然月租费貌似便宜，但也经不起长时间的累积。100个替代昂贵商业软件的开源应用尽管有许多好理由，但避免或减少使用费，仍然是许多用户看中开源应用软件的主要因素。基于这一点，我们更新了可替代_citadel开源中文版本
竞选计算机协会网络部部长,2019年计算机协会部长竞选演讲稿-程序员宅基地
文章浏览阅读55次。2019年计算机协会部长竞选演讲稿篇一:计算机协会部长竞选演讲稿尊敬的领导，敬爱的老师，亲爱的同学们：大家晚上好！俗话说：马只有驰骋千里，方知其是否为良驹；人只有通过竞争，才能知其是否为栋梁。我是来自ｘｘｘ班的伍朝海，今晚，我很荣幸能够站在这里参加这次学生会的竞选，职位是ｘｘ系的宣传窗口——新闻网络部的负责人。我知道，今晚竞选的不仅仅是个职位，也是在竞选一个为同学们服务的机会，更是在竞选一个为我们...
随便推点
stable diffusion(1): webui的本地部署(windows)_sd webui torch版本-程序员宅基地
文章浏览阅读2.1k次。有一个坑一直没过去，就是如果整体环境没完全装好，但是使用我自己提前创建的python虚拟环境来启动SD启动脚本stable-diffusion-webui/webui-user.bat，期间会因为某些原因（比如没梯子东西下载不下来）启动失败，但是第二次启动时就会报没有pip模块的错误，我就只能重新创建python虚拟环境，再装一遍包，这个过程很漫长很浪费时间，所以一定跟着我的脚步，一步不要落下的走，心急吃不了热豆腐。如果没有梯子，这里很慢或者根本过不去，所以参考。三、修改url地址（梯子强可不改）_sd webui torch版本
CTFSHOW做题记录_ctfshow 龙猫-程序员宅基地
文章浏览阅读491次。CTFSHOW做题记录**CTFSHOW做题记录1**（菜菜的我要写日记啦，欢迎大佬指导）**密码学签到1给出“}wohs.ftc{galf”并且提示倒叙。**解题思路：没看提示的时候乍一看以为是栅栏密码，还想着用在线解密去做，但是定睛一看不对劲，再看题目原来就是倒叙。只需要反着来就好啦。**答案：flag{ctf.show}**今天也是元气满满的一天，好好学习。..._ctfshow 龙猫
抓取动态网页的数据的具体操作方法_动态加载的网页怎么获取链接-程序员宅基地
文章浏览阅读1.9k次。不同的方法适用于不同的情况，例如如果目标网站使用的是JavaScript动态加载数据，那么使用Scrapy-Splash可能会更加适合。如果目标网站的数据比较简单，那么使用浏览器开发者工具可能会更加方便。如果需要模拟用户的操作，那么使用Selenium可能是更好的选择。总之，需要根据具体情况选择合适的方法，才能高效地获取动态网页的数据。综上所述，选择合适的方法取决于具体的需求。如果需要模拟用户的操作，可以使用Selenium。动态网页是指在用户交互过程中，网页内容不断更新和变化的网页。_动态加载的网页怎么获取链接
Ubuntu20.04安装向日葵_ubuntu20.04 安装向日库-程序员宅基地
文章浏览阅读1k次，点赞3次，收藏6次。下载最新版本：https://sunlogin.oray.com/download/缺少部分依赖，手动下载：# 你知道最新的版本号了sudo wget http://download.oray.com/sunlogin/linux/SunloginClient-10.0.2.24779_amd64.debsudo wget http://mirrors.aliyun.com/ubuntu/pool/main/i/icu/libicu60_60.2-3ubuntu3_amd64.debsudo w_ubuntu20.04 安装向日库
JMeter之脚本录制_jmeter脚本录制，大厂软件测试高级多套面试专题整理集合-程序员宅基地
文章浏览阅读635次，点赞14次，收藏7次。打开IE浏览器，点击右上方工具按钮，依次选择“Internet选项” -> “连接” -> “局域网设置” -> “代理服务器”，勾选“为LAN使用代理服务器”，输入本地IP地址127.0.0.1及端口号8888，点击确定保存。若页面提示“此网站的安全证书存在问题”，点击“继续浏览此网站(不推荐) ”即可。4.选择“Requests Filtering”，在“包含模式”中填入“.+(baidu.com).+”用以过滤非。选中“工作台”，右键选择“添加” -> “非测试元件” -> “HTTP代理服务器”
20231114歌谣v3--学习篇-组件注册-props-程序员宅基地
文章浏览阅读326次，点赞8次，收藏10次。前端