今天,在队长的带领下学习了弗洛伊德算法。
一、弗洛伊德(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
点此复制本页地址
院徽作为学院的重要象征,承载着学院的文化底蕴和精神风貌。为了激发同学们的创作热情,增强学院内部的凝聚力,全面展现文法学院的特色与精神风貌,文法学院于4月10日至16日举办文法学院院……
郭小宇 户煜阳 河南科技学院新科学院法律系查看全文 >>
为深入贯彻落实文明教育理念,培养学生的劳动意识与奉献精神,新乡工程学院文法学院于4月27日中午在学院楼A-212教室开展了“文明教育日”劳动志愿服务活动,文法学院学生积极参与。活动开始……
冯云会 苏一飞 河南科技学院新科学院法律系查看全文 >>
为全面贯彻落实党的二十大和二十届二中、三中全会精神,巩固拓展学习贯彻习近平新时代中国特色社会主义思想主题教育成果,深化党纪教育成果,以常态长效治理确保贯彻落实中央八项规定精……
花婷婷 河南科技学院新科学院法律系查看全文 >>
为规范党员发展流程,提升党员发展质量,4月23日上午,文法学院教工党支部于学院楼B319书法实验室成功召开第32期拟发展对象民主评议大会。此次会议由教工党支部宣传委员段洁主持,教工党支……
王寒月 河南科技学院新科学院法律系查看全文 >>
为贯彻落实习近平法治思想,进一步增强师生法治意识,营造平安和谐的校园环境,4月25日上午九点,文法学院组织法学师生通过线上平台参加中国法治实务大讲堂第三讲学习活动。本次大讲堂以……
苏一飞 河南科技学院新科学院法律系查看全文 >>
为深入贯彻落实党的作风建设要求,进一步强化纪律意识和规矩意识,4月24日,文法学院党委理论中心组于书法实验室B-319召开深入贯彻中央八项规定精神学习教育会议。会议由党委副书记刘松梅主……
苏一飞 河南科技学院新科学院法律系查看全文 >>
为深入贯彻落实习近平总书记关于加强文化遗产保护传承、弘扬中华优秀传统文化的重要论述,4月17日,文法学院教师李婉鑫、马智慧、任多芳、朱雪珂带领学生代表,前往焦作市武陟县乔庙镇冯……
王玥忻 河南科技学院新科学院法律系查看全文 >>
为深入贯彻落实习近平总书记关于加强文化遗产保护传承、弘扬中华优秀传统文化的重要论述,4月17日,文法学院教师李婉鑫、马智慧、任多芳、朱雪珂带领学生代表,前往焦作市武陟县乔庙镇冯……
王玥忻 郝晓琳 河南科技学院新科学院法律系查看全文 >>