ACM模板——Floyd(弗洛伊德算法)
发布日期:2021-06-30 23:43:58
浏览次数:2
分类:技术文章
本文共 712 字,大约阅读时间需要 2 分钟。
一、理论:
如何求任意两点之间最短路径呢?通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索,即对每两个点都进行一次深度或广度优先搜索,便可以求得任意两点之间的最短路径。可是还有没有别的方法呢?
我们来想一想,根据我们以往的经验,如果要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点(顶点k),并通过这个顶点k中转即a->k->b,才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢?甚至有时候不只通过一个点,而是经过两个点或者更多点中转会更短,即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市(4->3)的路程e[4][3]原本是12。如果只通过1号城市中转(4->1->3),路程将缩短为11(e[4][1]+e[1][3]=5+6=11)。其实1号城市到3号城市也可以通过2号城市中转,使得1号到3号城市的路程缩短为5(e[1][2]+e[2][3]=2+3=5)。所以如果同时经过1号和2号两个城市中转的话,从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子,我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好,下面我们将这个问题一般化。
二、代码:
for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
转载地址:https://lux-sun.blog.csdn.net/article/details/82503163 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年05月01日 04时54分02秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
用原生java实现Spring以及SpringMVC(二)
2021-07-04
redis
2021-07-04
@FeignClient注解的重复名称解决
2021-07-04
ClassFile之Methods
2021-07-04
java.net.BindException: 无法指定被请求的地址
2021-07-04
scala list
2021-07-04
k8s设置阿里云仓库
2021-07-04
svn服务器安装
2021-07-04
spark 笔记1
2021-07-04
svn 没有作者信息) | (没有时间信息
2021-07-04
shell dirname basename
2021-07-04
线程分析
2021-07-04
jenkins
2021-07-04
DOM(总结)
2021-07-04
MySQL学习总结(一)
2021-07-04
MySQL学习总结(二)
2021-07-04
未来已至,5G加持下的云游戏将走向何方?
2021-07-04
Mysql常用删除方式比较
2021-07-04
备案问题汇总
2021-07-04