Floyd 算法小结

举报
Linux猿 发表于 2021/08/05 23:42:45 2021/08/05
【摘要】          学习完Floyd算法后,本想找个题做但没找到就先做一下总结吧! 算法思想: 最短距离有三种情况: 1、两点的直达距离最短。(如下图<v,x>) 2、两点间只通过一个中间点而距离最短。(图<v,u>) 3、两点间用通过两各以上的顶点而距离最短。(图<...

         学习完Floyd算法后,本想找个题做但没找到就先做一下总结吧!

算法思想:
最短距离有三种情况:
1、两点的直达距离最短。(如下图<v,x>)
2、两点间只通过一个中间点而距离最短。(图<v,u>)
3、两点间用通过两各以上的顶点而距离最短。(图<v,w>)
对于第一种情况:在初始化的时候就已经找出来了且以后也不会更改到。
对于第二种情况:弗洛伊德算法的基本操作就是对于每一对顶点,遍历所有其它顶点,看看可否通过这一个顶点让这对顶点距离更短,也就是遍历了图中所有的三角形(算法中对同一个三角形扫描了九次,原则上只用扫描三次即可,但要加入判断,效率更低)。
对于第三种情况:如下图的五边形,可先找一点(比如x,使<v,u>=2),就变成了四边形问题,再找一点(比如y,使<u,w>=2),可变成三角形问题了(v,u,w),也就变成第二种情况了,由此对于n边形也可以一步步转化成四边形三角形问题。(这里面不用担心哪个点要先找哪个点要后找,因为找了任一个点都可以使其变成(n-1)边形的问题)。

   Floyd算法就是每次在两点之间插入一点,看是否路径更短,如果更短则更新其值。相当于一个多边形不断缩小,不断进行优化。

代码(模版):


      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];
  
 

调用它之前先初始化:d[ i ][ i ]=0 ;如果两个点不相连则令其为无穷大;

代码(权值很大的情况):


      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]<INF&&d[k][j]<INF)
       d[i][j]=d[i][k]+d[k][j];
  
 

INF的值必须大于权值中的最大值。

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/9419243

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。