首页 > 编程语言 >Floyd算法的简单使用方法(模板)

Floyd算法的简单使用方法(模板)

时间:2024-05-27 18:01:30浏览次数:27  
标签:初始化 Form int 路径 算法 Floyd 模板

今天我们老师讲了Floyd算法,使用想着总结一下,方便后面进行复习,使用如果在接下来的文章中有哪里写的不对,或者表达不恰当,欢迎提出,谢谢!

关于这个算法,我的理解是应用链接矩阵来进行存储值,通过比较来更新值,最后得出最短路径等问题的答案;

使用模板:

第一步就是使用宏定义来定义一个偏大的值,作为后面初始化的值,如:

#define inf 9999999

切记,后面不要加引号;

当然也可以这样来定义:

memset(Form, 0b00111111, sizeof(Form)); 

 这里的From是数组名字;

需要取数组里面的值的话可以这样:

int x=Form[0][0];

随后定义一个链接矩阵,也就是一个二维数组,如:

    int D[501][501];

 根据题目的不同,对矩阵里面的值进行初始化;

如:

        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                D[i][j]=inf;

 这里初始化时需要注意,题目提供的图是不是无向图,还是有向图;

从而对应初始化的值;

如无向图是这样的

        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                D[i][j]=inf;
        for(int i=0;i<e;i++){
            cin>>x>>y>>c;
            D[x][y]=c;
            D[y][x]=c;
        }

 无向图在初始化时,每个坐标会分别对应两个值;

接下来就是以每个顶点作为中间点,来比较两边的路径相加是否比直通的路径权小,如果是比其小的话,更新值;

如:

        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(D[i][j]>D[i][k]+D[k][j])
                        D[i][j]=D[i][k]+D[k][j];

 好了,算法的表达部分就是到这里了,后面的内容就要看题目给的要求了;

例题详情见文章:最短路径算法(Floyd-Warshall)    及    双十一;

标签:初始化,Form,int,路径,算法,Floyd,模板
From: https://blog.csdn.net/wang3074162725/article/details/139144513

相关文章

  • 7-4 并查集【模板】
    给出一个并查集,请完成合并和查询操作。输入格式:第一行包含两个整数N、M,表示共有N个元素和M个操作。接下来M行,每行包含三个整数Zi​、Xi​、Yi​。当Zi​=1时,将Xi​与Yi​所在的集合合并。当Zi​=2时,输出Xi​与Yi​是否在同一集合内,是的话输出Y;否则的话输出N。输出格式:......
  • springboot3+Thymeleaf 模板一直找不到的原因。
    1<build>2<resources>3<resource>4<directory>src/main/java</directory>5<includes>6<include>**/*.yml</include>7......
  • 七大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、归并排序、快速排序
    以下内容转载自文章1.插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找到已排序元素中小于等于tem的元素5.tem插入到该元素的后面,如果已排序所有元......
  • 记一次攻防演练中的若依(thymeleaf 模板注入)getshell
    记一次攻防演练中幸运的从若依弱口令到后台getshell的过程和分析。0x01漏洞发现首先,我会先把目标的二级域名拿去使用搜索引擎来搜索收集到包含这个目标二级域名的三级域名或者四级域名的网站。这样子可以快速的定位到你所要测试的漏洞资产。1、推荐三个比较实用的搜索引擎:奇......
  • 算法训练 | 二叉树Part3 | 104.二叉树的最大深度、111.二叉树的最小深度、222.完全二
    目录104.二叉树的最大深度递归法⭐迭代法111.二叉树的最小深度递归法⭐迭代法222.完全二叉树的节点个数普通二叉树完全二叉树嵌入式学习分享个人主页:Orion嵌入式随想录-小红书(xiaohongshu.com)104.二叉树的最大深度题目链接:104.二叉树的最大深度-力扣(Le......
  • 算法训练 | 二叉树Part4 | 10.平衡二叉树、257.二叉树的所有路径、404.左叶子之和
    目录110.平衡二叉树递归法迭代法257.二叉树的所有路径递归法迭代法404.左叶子之和递归法迭代法110.平衡二叉树题目链接:leetcode.cn文章讲解:代码随想录递归法解题思路高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。要求......
  • 算法训练 | 二叉树Part2 | 层序遍历、226.翻转二叉树、101.对称二叉树
    目录广度优先226.翻转二叉树递归法⭐迭代法层序法101.对称二叉树后序遍历法⭐迭代法嵌入式学习分享个人主页:Orion嵌入式随想录-小红书(xiaohongshu.com)广度优先解题思路层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。需要借用一个辅助数据......
  • C++程序分享--常见算法/编程面试题:(百度笔试题)用 C 语言实现函数 void * memmove
    关注我,持续分享逻辑思维&管理思维&面试题;可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导;有意找工作的同学,请参考博主的原创:《面试官心得--面试前应该如何准备》,《面试官心得--面试时如何进行自我介绍》, 《做好面试准备,迎接2024金三银四》。【图解《程序员面试常见的......
  • 基于yolov2深度学习网络的单人口罩佩戴检测和人脸定位算法matlab仿真
    1.算法运行效果图预览   2.算法运行软件版本MATLAB2022A 3.算法理论概述      基于YOLOv2(YouOnlyLookOnceversion2)深度学习网络的单人口罩佩戴检测和人脸定位算法是一种结合了目标检测与特征识别的综合性解决方案,主要用于自动检测图像或视频中人物......
  • 淘宝在线扭蛋机一番赏中低层代码权重算法是怎么运作的
    权重算法在抽赏功能中的运用主要体现在通过设定不同选项的权重值,来决定它们被抽中的概率。具体来说,权重越大的选项,在抽奖时被选中的概率就越大。在抽赏功能的实现中,可以采用带权重的随机算法(WeightedRandomAlgorithm)。这种算法的基本思路是:首先,累加每个选项的权重值,得到一个......