当前位置: 主页 > 社会实践 >

披坚执锐,所向披靡

来源:许昌学院弘毅书院 作者:张亚坤

今天,在队长的带领下学习了弗洛伊德算法。

一、弗洛伊德(Floyd)算法的概念

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似

二、弗洛伊德(Floyd)算法与迪杰斯特拉算法区别

1.迪杰斯特拉算法通过选定的被访问顶点,求出从出发访问顶点到其他顶点的最短路径; 弗洛伊德算法中每一个顶点都是出发访问点,所以需要将每一个顶点看做被访问顶点,求出从每一个顶点到其他顶点的最短路径。

2.Floyd算法,则修正了dijkstra算法对于边权为负问题的不足,引入了一个外循环,来遍历每个点,从而查询该点是不是在i和j之间,这样的话,无论边权为负值还是正值,都会被考虑进去。对于邻接矩阵A来说,在k-1次迭代后,A(k-1)[i][j]为所有从顶点i到j且不经过k之后的顶点的最小长度,有可能经过k之前的点。所以在遍历过程中需要比较A[i][j]与A[i][k]+A[k][j]的大小,取小值,表示比较经过k点与不经过k点的路径长度大小。

三、弗洛伊德(Floyd)算法的基本思想

设置顶点vi到顶点vk的最短路径已知为Lik,顶点vk到vj的最短路径已知为Lkj,顶点vi到vj的路径为Lij 则vi到vj的最短路径为:min((Lik+Lkj),Lij(直连)),vk的取值为图中所有顶点,可获得vi到vj的最短路径。

四、弗洛伊德(Floyd)算法的步骤

1 .使用二维数组dis储存路径,同时最终状态代表点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)!

2 .从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。

3. 而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。

4 .重复上述直到最后插点试探完成。最终dis数组中存放的就是任意两个结点之间的最短距离。

学习应当"披坚执锐,所向披靡",拥有一往直前的精神。

http://www.dxsbao.com/shijian/472197.html 点此复制本页地址

相关内容

河北大学团队:聚焦农村老人社会参与,助力城乡融合发展

河北大学团队:聚焦农村老人社会参与,助力城乡融合发展为积极响应国家应对人口老龄化战略,推动城乡融合发展,2025年3月2日至2025年3月15日,来自河北大学的一支大学生团队深入河北省保定市…… 蔡燕虹 河北大学管理学院查看全文 >>

推荐内容

“红岩青梦”实践队赴困牛山:追寻红色记忆,助力乡村振兴

2025年2月17日,遵义医科大学珠海校区“红岩青梦”实践队怀着崇敬的心情,踏上了贵州省石阡县困牛山这片红色热土,开展“困牛…

闽南科技学院校团委读书社开展红色电影观影活动

为引领广大闽科学子筑牢爱国根基,赓续红色血脉,弘扬革命传统,激励同学们在新时代征程中奋勇前行,闽南科技学院校团委读书…

 延续十九载,湖南农大机电学院打造科技人文融合志愿服务,为特殊儿童送暖

3月30日上午,湖南农业大学机电工程学院青年志愿者服务队冒雨走进长沙市阳光特殊儿童服务中心,以舞蹈表演、机器人演示、手工…

礼仪赋能成长——共建校园文明新高度

为深化校园精神文明建设,增强大学生文明礼仪意识,进一步提升学生干部的综合素养与个人风貌。3月12日下午,闽南科技学院校“…

辨明前路,引航梦想 ——人文学院举办公考指导分享会

为帮助人文学子把握公考方向,了解相关政策,3月27日,人文学院于院办202教室举办公考指导分享会,邀请南京大学博士王海霞老师…

最新发布

三下乡活动开班仪式暨师生见面会
7月8日,“星梦”社会实践队在茂名市化州市杨梅镇中心小学举行开班仪式,为促进队员与学生对彼此的了解,对彼此有初步的认识和了解,“星梦”实践队开展了师生见面会,为三下乡活动的开展奠定基础。早上,队…
三下乡“点点星火”实践队|绘希望灯塔,筑七彩年华
绘画,是人类的第二种语言文字,它同诗歌、散文一样,能够抒发作者的情感,表达当时的意境,也同书法、文章一样,有自己风格的体现。千人千画,绘画能够很好的激发人的想象力、创造力,通过绘画,将眼睛看到…
普及法律知识,构建和谐社会
普及法律知识,构建和谐社会——乡村振兴促进团于紫荆台村开展青少年普法宣讲活动为全面推进依法治国,加快建设社会主义法治国家,增强青少年的法治意识,7月15日上午,河南师范大学法学院“法治你我同行,助…
开启乡村振兴新篇章——曲阜师范大学政治与公共管理学院乡村振兴青研团实践队
产业是乡村振兴的基础。陈疃镇将发展蓝莓特色产业作为富民强镇的“助推器”。发挥蓝莓标准化种植基地示范带动作用,共建“日照蓝莓”品牌,品牌效应日渐凸显,市场认可度逐步提升。同时不短加强政校合作,积…
趣味运动会进塘边,体育魅力无限
7月16日上午,岭师“破浪”社会实践队在塘边举行了“我运动,我快乐,我健康”的运动会。炎炎夏日,室外温度高,可是也没有浇灭学生对体育活动的热爱。塘边学生对体育的热情渲染周围所有“破浪”社会实践队的…
重走长征足迹,传承红色基因
重走长征足迹,传承红色基因——“回味百年经典,传承党史基因”法学院党史学习教育团开展何家冲红色宣讲活动为普及党史文化,追溯红色记忆,7月14日上午,河南师范大学法学院“回味百年党史,传承红色经典”…
“点点星火”社会实践队|生命在于运动
“一二三四五六七八,二二三四五……”清晨的房间里传出声声口号。这是“点点星火”社会实践队成员吴国菘老师在给学生们上体育健身课。运动是一切生命的源泉。没有运动也就没有了生命,缺少运动的生命是短暂…
“追忆峥嵘岁月,赓续精神血脉”红色寻访暑期社会实践活动
为引导广大青年重温峥嵘岁月,铭记红色历史,赓续共产党人的精神血脉,牢记初心、奋楫笃行,7月12日,郑州轻工业大学机电工程学院“追忆峥嵘岁月,赓续精神血脉”暑期社会实践小队赴江苏省连云港市抗日山烈士…
学党史 践初心 跟党走——党史知识竞答
7月10日,为了培养学生爱党爱国情怀,拓宽学生视野,发扬红色精神,传承红色基因,迎接二十大的到来,“星梦”实践队开展了党史知识竞答活动。中午,队员们吃完午饭后就开始布置教室,为党史知识竞赛活动的开…
岭师学子三下乡:西洋乐器绎经典,奏响时代最强音
“追寻”文化支教队讯(通讯员杨颖)2014年习近平总书记《在文艺工作座谈会上的讲话》中指出:“我们要结合新的时代条件传承和弘扬中华优秀传统文化,传承和弘扬中华美学精神。”为了让乡村学生进一步认识音…