弗洛伊德算法——C语言

弗洛伊德算法,是一种用于解决所有顶点对之间最短路径问题的经典算法,该算法通过动态规划的方法计算出从每个顶点到其他所有顶点的最短路径。

弗洛伊德算法的基本思想是逐步考虑每一个顶点作为中间点,更新所有顶点对之间的最短路径。它通过以下三个步骤实现:

1.初始化距离二维数组,类似于这样:

2.加入中间节点,遍历每一对顶点,看距离是否减小。这里说明一下:以二维数组G->arc[i][j] 为例,G->arc[i][j]表示的是顶点 i 到达顶点 j 的距离,如果是G->arc[i][k]+G->arc[k][j],就是顶点 i 先到中转点 k 再到顶点 j 的距离,这就是如何计算经过中转点后两顶点的距离。

3.更新矩阵,如果 G->arc[i][j] > G->arc[i][k]+G->arc[k][j],那么最小距离就更新了,为G->arc[i][k]+G->arc[k][j]

代码主体如下:

void floyd(Graph* G) {int** S = (int**)malloc(sizeof(int*) * G->vexsNum);for (int i = 0; i < G->vexsNum; i++) {S[i] = (int*)malloc(sizeof(int) * G->vexsNum);}for (int i = 0; i < G->vexsNum; i++) {for (int j = 0; j < G->vexsNum; j++) {S[i][j] = G->arcs[i][j];}for (int k = 0; k < G->vexsNum; k++) {for (int j = 0; j < G->vexsNum; j++) {for (int i = 0; i < G->vexsNum; i++) {if (S[j][i] > S[j][k] + S[k][i]) {S[j][i] = S[j][k] + S[k][i];}}}}for (int i = 0; i < G->vexsNum; i++) {for (int j = 0; j < G->vexsNum; j++) {printf("%d ", S[i][j]);}printf("\n");}
}

第一个for循环是为S二维数组距离数组开辟空间,模拟二维数组的生成。

第二个大的for循环是把S数组进行初始化,接收外界array数组的值。

第三个大的for循环中,k 代表着遍历每个顶点并且将它作为中转点,后面的 j 和 i 代表遍历每一对顶点,然后比较是否加入中转点的距离大小,进而更新。

当然我们也可以标记出顶点的中间节点(因为加入中转点会导致顶点的前驱改变),除了正常的初始化中间节点数组之外,如果距离为Max赋值为-1,否则赋值为 i:

	for (int i = 0; i < G->vexsNum; i++) {for (int j = 0; j < G->vexsNum; j++) {S[i][j] = G->arcs[i][j];if (G->arcs[i][j] != 0&&G->arcs[i][j]!=Max) {P[i][j] = i;}else {P[i][j] = -1;}}}

还有在for循环中更新P数组的值:更新中间节点为中转点。

	for (int k = 0; k < G->vexsNum; k++) {for (int j = 0; j < G->vexsNum; j++) {for (int i = 0; i < G->vexsNum; i++) {if (S[j][i] > S[j][k] + S[k][i]) {S[j][i] = S[j][k] + S[k][i];P[j][i] = k;}}}}

最后结构如下:

        可以看见顶点之间的最短距离更新了,对比图会发现,两顶点的中间节点也更新了,例如顶点3 和顶点 2的中间节点更新为顶点1 ,这时得出的最短距离是 4 。

这就是文章的全部内容了,希望对你有所帮助,如有错误欢迎指出。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/351643.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mySql的事务(操作一下)

目录 1. 简介2. 事务操作3. 四大特性4. 并发事务问题5. 脏读6. 不可重复读7. 幻读事务隔离级别参考链接 1. 简介 事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这些操作…

html是什么?http是什么?

html Html是什么&#xff1f;http是什么&#xff1f; Html 超文本标记语言&#xff1b;负责网页的架构&#xff1b; http(&#xff08;HyperText Transfer Protocol&#xff09;超文本传输协议&#xff1b; https&#xff08;全称&#xff1a;Hypertext Transfer Protocol …

VMware 桥接网络突然无法上网

VMware 桥接网络突然无法上网 0. 问题1. 解决方法 0. 问题 昨天&#xff0c;VMware 桥接网络正常使用&#xff0c;今天突然无法上网。 1. 解决方法 打开VMware的虚拟网络编辑器&#xff0c;将桥接模式的网络从“自动”改成你要使用的网卡&#xff0c;问题解决。 完成&#…

Numpy

文章目录 一、数据维度的概念1.1常见的多维数据1.2numpy的维度、形状、轴1.2.1维度1.2.2形状1.2.3轴 1.3reshape()函数1.4numpy中行、列向量的表示1.5数组的迭代1.6添加/删除元素1.6.1append()1.6.2insert()1.6.3delete() 二、Ndarray对象2.1简介2.1.1常用属性2.1.2.ndarray对象…

Python | Leetcode Python题解之第160题相交链表

题目&#xff1a; 题解&#xff1a; class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:A, B headA, headBwhile A ! B:A A.next if A else headBB B.next if B else headAreturn A

Office办公软件如何下载安装?Office 2021最佳的办公软件安装包资源分享!

Office软件这种文档格式的普及&#xff0c;得益于其高度的兼容性和通用性&#xff0c;使得用户能够轻松地在不同的电脑和平台上打开和编辑文件。 Office软件文档格式的通用性&#xff0c;意味着无论是Windows、macOS还是Linux等操作系统&#xff0c;用户都能无障碍地打开和浏览…

【源码】16国语言交易所源码/币币交易+期权交易+秒合约交易+永续合约+交割合约+新币申购+投资理财/手机端uniapp纯源码+PC纯源码+后端PHP

测试环境&#xff1a;Linux系统CentOS7.6、宝塔面板、Nginx、PHP7.3、MySQL5.6&#xff0c;根目录public&#xff0c;伪静态laravel5&#xff0c;开启ssl证书 语言&#xff1a;16种&#xff0c;看图 这套带前端uniapp纯源码&#xff0c;手机端和pc端都有纯源码&#xff0c;后…

经典电源电路基础(变压-整流-滤波-稳压)

1.电源电路的功能和组成 电子电路中的电源一般是低压直流电&#xff0c;先把220v交流电变换成低压直流电&#xff0c;再用整流电路变成脉动的直流电&#xff0c;最后用滤波电路滤除掉脉动直流中的交流成分后才能得到直流电。有的电子设备对电源的质量要求很高&#xff0c;所以…

用Copilot画漫画,Luma AI生成视频:解锁创意新玩法

近年来&#xff0c;随着人工智能技术的不断发展&#xff0c;各种创意工具也层出不穷。今天&#xff0c;我们就来介绍一种全新的创作方式&#xff1a;使用Copilot画漫画&#xff0c;再将漫画放入Luma AI生成视频。 Copilot&#xff1a;你的AI绘画助手 Copilot是一款基于人工智…

python之对接有道翻译API接口实现批量翻译

内容将会持续更新&#xff0c;有错误的地方欢迎指正&#xff0c;谢谢! python之对接有道翻译API接口实现批量翻译 TechX 坚持将创新的科技带给世界&#xff01; 拥有更好的学习体验 —— 不断努力&#xff0c;不断进步&#xff0c;不断探索 TechX —— 心探索、心进取&…

深度神经网络——深度学习中的 RNN 和 LSTM 是什么?

引言 自然语言处理和人工智能聊天机器人领域许多最令人印象深刻的进步都是由 递归神经网络&#xff08;RNN&#xff09; 和长短期记忆&#xff08;LSTM&#xff09;网络。 RNN 和 LSTM 是特殊的神经网络架构&#xff0c;能够处理顺序数据&#xff0c;即按时间顺序排列的数据。…

款基于SpringBoot+Vue+ElementUI技术栈开发的自定义表单工具(已开源)

TDuck填鸭表单是一个开源的问卷调查系统&#xff0c;一款基于SpringBootVueElementUI技术栈开发的自定义表单工具&#xff0c;它不仅支持问卷调查&#xff0c;还能进行数据收集。TDuck团队经过两年的优化&#xff0c;使得社区版功能趋于稳定。2023年5月&#xff0c;团队推出了可…

HTML静态网页成品作业(HTML+CSS)—— 明星吴磊介绍网页(5个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有5个页面。 二、作品演示 三、代…

http穿透怎么做?

众所周知http协议的默认端口是80&#xff0c;由于国家工信部要求&#xff0c;域名必须备案才给开放80端口&#xff0c;而备案需要固定公网IP&#xff0c;这就使得开放http80端口的费用成本和时间成本变的很高。那么能不能利用内网穿透技术做http穿透呢&#xff1f;下面我就给大…

VMware Workstation 16安装ESXI7.0

一、新建虚拟机 根据新建虚拟机向导新建虚拟机&#xff0c;这里不在展示。 二、挂载ESXI7.0镜像 三、安装ESXI操作系统 1、打开电源 2、选择安装ESXI 回车&#xff0c;F11 选择安装位置&#xff0c;我这里只添加了一块盘&#xff0c;不用选择&#xff0c;回车 选择键盘&…

ComfyUI

文章目录 一、关于 ComfyUI特点快捷键QA你为什么做这个&#xff1f;这是给谁的&#xff1f; 二、安装1、Windows直接链接下载如何在另一个UI和ComfyUI之间共享模型&#xff1f; 2、Jupyter Notebook3、手动安装&#xff08;Windows、Linux&#xff09;AMD GPU&#xff08;仅Lin…

CloudFlare 里如何设置参数传递的 301 重定向

自从接到【哈哈,笑死我了都,黔驴技穷了都!】一文里提到的代维客户订单,这两天明月就一直在加班加点的重新部署着客户的四个服务器,因为有三个都是 WordPress+WooCommerce 式的电商平台,很是有些费时费力,好在现在基本都搞定了,剩下的就是些细节方面的优化、调整了。期间…

深入了解RSA加密算法

目录 前言 一、什么是RSA&#xff1f; 二、RSA加密的基本概念 1.非对称加密 2.密钥生成 3.加密和解密 三、RSA加密的工作原理 四、RSA的应用场景 五、RSA加密解密的实现 六、RSA算法的局限性及改进措施 前言 在当今的数字化时代&#xff0c;信息的安全性成为了人们关注…

mongodb command

1. start and stop ./mongod --dbpath -dbpath /data/shard1/db --logpath -dbpath /data/shard1/db/logs/mongodb.log --fork mongod --shutdown --dbpath /data/shard1/db MongoDB基础篇-03-启动与关闭_mongodb启动和关闭-CSDN博客 2. 查看分片数据分布 mongo mongo01.c…