【关系闭包】传递闭包 Warshall Floyd

(参考自:《离散数学》&  博客https://blog.csdn.net/ljhandlwt/article/details/52096932)

Warshall算法比较冷门,在这里不细说,贴个书上伪代码翻译过来的代码

【关系闭包】传递闭包 Warshall Floyd
 1     for(int i=0;i<maxn;++i) //行 
 2     for(int j=0;j<maxn;++j) //列 
 3     {
 4         if(Graph[i][j]){
 5             for(int k=0;k<maxn;++k){//在第i列中找
 6                 //遍历行
 7                 if(Graph[k][i])
 8                     Graph[k][j]=1;
 9             } 
10         }
11     }
View Code

主要谈谈Floyd算法,因为之前做题的时候在一个坑上栽了很久: 

  Floyd 的中转节点为最外层遍历!!

·遍历的次序 中转节点在最外层

 

For(k)   //中转节点

  For(i) 

    For(j)

      If()  { 松弛 ;}

每次的松弛操作 val[i][j] = max/min(val[i][j], val[i][k]+val[k][j]),如果是将k放在最内层,则i和j之间的松弛是一遍松弛完,则只有在i和k,k和j间的权值都已经取到min或max时,才能实现i和j之间取到最值,然而这在大多数情况下是不能满足的。

而将中间点k放在最外层,那么在i到j的点集中(不含ij,假设是顺序编号,之后可以推广到非顺序编号,即将ij之间能连通的店自己默认编号),假设编号最大为m,那么在外层循环k取到m时,val[i][j]必然取到了最小值(以最小值为例,最大值类似)

 

用归纳法证明:

m1为i到h中的最大编号,m2为h到j中的最大编号--> i<m1<m2<j

假设结论成立,则k==m1时 val[i][h]已经取到最小值,k==m2时 val[h][j]已经取到最小值又因为m2是ij中编号最大的,m2是最后一次遍历,则执行松弛操作

  val[i][j] = max/min(val[i][j], val[i][k]+val[k][j])

此时 ,由之前的推论val[i][k]和val[k][j]都已经取到最小值,那么对应的val[i][j]也取到其最小值

 

有时候,用Floyd来进行传递闭包的操作,同样要将节点的遍历放在最外边:

 若将k放在最里层,那么传递操作 val[i][j] |= val[i][k] & val[k][j] ,ij之间的传递只有一遍,那么则要保证i k之间k j之间已经达到最大连通时,ij传递操作后才能达到最大的连通,然而放在最内层大多数情况下不满足,只有放在最外层遍历才可以,证明与上边的类似,在这不赘述。

综上所述,Floyd的遍历,节点要放在最外层!!

 

 

 

上一篇:多源最短路算法——Floyd算法


下一篇:C - Anna, Svyatoslav and Maps floyd