warshell
Warshell 算法 用来求有向图的传递闭包
设R的关系矩阵为M
Mt为在R关系上的传递闭包那么：
Mt = M + M^2 + M^3 +......M^n;
Warshell 算法(时间复杂度O(n^3))
思想：动态规划(记忆式)
用动态规划求关系的传递闭包
#include<iostream>
using namespace std;
bool M[100][100];//布尔数组;
void main()
{
int n;
cout<<"请输入矩阵维数：";
cin>>n;
cout<<"请输入关系矩阵："<<endl;
int i,j,k;
while(n)
{
for(i =1; i <= n; i++)
for(j = 1; j <= n; j++)
cin>>M[i][j];
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
M[i][j] = M[i][j] + M[i][k]*M[k][j];//布尔数进行的是逻辑加乘;
cout<<"传递闭包："<<endl;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
cout<<M[i][j]<<" ";
cout<<endl;
}
}
}