1. 首页
  2. 最短路

Floyd求最小环

算法引入:

*求一个图G中的最小环路的朴素算法为:每次找到一条边,删除了求这两点之间的最短路径;

*若能求出,则这条最短路径与原来的边构成一个环,不过时间复杂度略高;

*算法思想;

*Floyd算法是按照顶点的编号增加的顺序更新最短路径的;

*如果存在最小环,则会在这个环中的点编号最大的那个点u更新最短路径之前发现这个环;

*即当点u被拿来更新ij的最短路径的时候,可以发现这个闭合环路;

*发现的方法是,更新最短路径前,遍历i,j点对,一定会发现某对ij的最短路径长度:

*dist[i][j]+map[j][u]+map[u][i]!=INF,这时sij是当前环中挨着点u的两个点;

*因为在之前的最短路径更新过程中,u没有参与更新,所以dist[i][j]所表示的路径中不会有点u,即一定为一个环;

*

*如果在每个新的点拿来更新最短路径之前遍历ij验证上面的式子,虽然不能遍历到所有的环;

*但是由于dist[i][j]ij点的最短路径m所以肯定可以遍历到最小的环;

*

*如果有负权环,则该算法失效,因为包含负环的图上,dist[i][j]已经不能保证ij的路径上不会经过同一个点多次了;

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1411 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01
  2. .02