warshall算法求传递闭包矩阵
其具体过程如下
设在n个元素的有限集上关系R的关系矩阵为B：
（1）置新矩阵A=B;
（2）置k=1;
（3）i ←1;
（4）对j=1,2,3,4…n做A[i,j]←A[i,j]∨（A[i,k] ∧ A[k,j]);
（5） i ←i+1; if i<=n,then goto4
（6）k ←k+1 ，if k<=n,then goto3,else停止。
所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。
改良！： A[i,j]∨（A[i,k] ∧ A[k,j])这一步骤可以简化为：当 A[i,k]！=0时，原式等价于 A[i,j]∨ A[k,j]，当 A[i,k]==0时，原式 A[i,j] 不变。
个人理解：对于原矩阵，原本等于1的地方（也即 A[i,j]=1时，不管可不可以插入一个新的过渡点，都应该为1 ），对于原矩阵，原本等于0的地方需要我们判断是不是可以插入一个新的点来更新原本此位置的值。而此时的k的循环就是控制插入点的位置。而i,j的循环分别控制矩阵的行和列。k循环在最外层是为了先一层一层插入防止发生错误。
代码如下
#include<stdio.h>
#define M 100
#define N 100
int main()
{
int n,i,j,k;
int a[M][N];
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][k]!=0)
a[i][j]=a[i][j]|a[k][j];
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
